akhauriyash/Code-Regression huggingface dataset:
// header {{{
#include <bits/stdc++.h>
using namespace std;

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

struct E {
    int to;
    double w;
};

using G = vector<vector<E>>;

template <typename T>
pair<vector<T>, vector<int>> dijkstra(G g, int s, T inf) {
    int n = g.size();
    vector<T> d(n, inf);
    vector<int> r(n, -1);
    d[s] = 0;
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, s});
    while(!pq.empty()){
        auto c = pq.top();pq.pop();
        if(d[c.second] < c.first) continue;
        for(auto e : g[c.second]){
            if(d[e.to] > d[c.second] + e.w){
                d[e.to] = d[c.second] + e.w;
                r[e.to] = c.second;
                pq.push({d[e.to], e.to});
            }
        }
    }
    return {d, r};
}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    vector<double> x, y, r;
    double sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    x.pb(sx);y.pb(sy);r.pb(0);
    x.pb(tx);y.pb(ty);r.pb(0);
    int n;cin >> n;
    inc(i, 0, n){
        double xx, yy, rr;
        cin >> xx >> yy >> rr;
        x.pb(xx);y.pb(yy);r.pb(rr);
    }
    n += 2;
    
    G g(n);

    inc(i, 0, n){
        inc(j, 0, n){
            if(i == j) continue;
            double dx = x[i]-x[j];
            double dy = y[i]-y[j];
            double d = max(0.0, sqrt(dx*dx + dy*dy) - r[i] - r[j]);

            g[i].pb({j, d});
        }
    }

    auto ans = dijkstra<double>(g, 0, 1e20).first[1];

    printf("%.12lf\n", ans);

    return 0;
}


Measured memory_bytes: 38000
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    sub_tree = []
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        sub_tree.append(size)
        res += size
    if N != res:
        sub_tree.append(N - res)
    memo[s].extend(sub_tree)
    return res


dfs(1)
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow2[N - 1] - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow2[x] - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow2[N]
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

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

#define int long long
#define str string
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
#define vint vector<int>
#define vchar vector<char>
#define vstr vector<string>
#define pb(n) push_back(n)

signed main(){
  int A,B,N=0,M,count=0,count2=0,count3=0,stack=0;
  str S,T;
  int C='A'-'a';
  cin>>A>>B;
  vchar V(A+B+1);
  rep(0,A+B+1)cin>>V.at(i);
  rep(0,A)if(isdigit(V.at(i)))count+=1;
  rep(A+1,A+B+1)if(isdigit(V.at(i)))count2+=1;
  if(V.at(A)=='-'&&A==count&&B==count2)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

using namespace std;

const long vmax=100001;

int main(){
 long n; 
  cin >> n;
  
  vector<long> e(vmax,0),o(vmax,0); 
  
  
  for(int i=0;i<n;i++){
    long v;
    cin >> v;
    if(i%2) o[v]++;
    else e[v]++;
  }
  
  long e1=0,e2=0,o1=0,o2=0; //Index
  for(int i=0;i<=vmax;i++){
   if(e[i]>e[e1]){ e2=e1;
                e1=i;
               }
   else if(e[i]>e[e2]) {
     e2=i;}
  
     if(o[i]>o[o1]){ o2=o1;
                o1=i;
               }
   else if(o[i]>o[o2]) {
     o2=i;}
  }
  
  if(e1==o1) cout << min(n-e[e1]-o[o2],n-e[e2]-o[o1]) << endl;
  else cout << n-e[e1]-o[o1] << endl;  
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using ll = long long;
using namespace std;

vector<ll> AB;
vector<ll> ans;

int main() {
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<ll> A(X);
    vector<ll> B(Y);
    vector<ll> C(Z);
    rep(i, X) cin >> A[i];
    rep(i, Y) cin >> B[i];
    rep(i, Z) cin >> C[i];
    sort(rall(C));

    rep(x, X) rep(y, Y) {
        AB.push_back(A[x] + B[y]);
    }
    sort(rall(AB));

    rep(i, min(X*Y, K)) rep(z, min(K, Z)) {
        ans.push_back(AB[i] + C[z]);
    }
    sort(rall(ans));

    rep(i, K) cout << ans[i] << endl;
}


Measured memory_bytes: 43240
#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use proconio::marker::{Isize1, Usize1, Bytes, Chars};
#[proconio::fastout]
fn main() {
    proconio::input!{
        n: usize,
        m: usize,
        obs: [u64; n],
        roads: [(Usize1, Usize1); m],
    }
    let mut link_info: Vec<Vec<u64>> = vec![vec![]; n];
    for (a, b) in roads {
        link_info[a].push(obs[b]);
        link_info[b].push(obs[a]);
    }
    let mut ans = 0;
    for i in 0.. n {
        if link_info[i].iter().all(|height| *height < obs[i]) { ans += 1; }
    }
    println!("{}", ans);
}


Measured memory_bytes: 12204
N=int(input())
ans=[0]*N
def nex(a,ls):
  x=(-a)%ls[2]
  return max([ls[1],a+x])+ls[0]
M=N-1
for i in range(M):
  station=[int(s) for s in input().split()]
  for j in range(i+1):
    ans[j]=nex(ans[j],station)
for e in ans:
  print(e)

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

ll n,d,a;
vector<P> M;

int main(){
    cin >> n >> d >> a;
    vector<ll> X;
    rep(i,n){
        ll x,h; cin >> x >> h;
        M.push_back(make_pair(x,h));
        X.push_back(x);
    }
    sort(M.begin(),M.end());
    sort(X.begin(),X.end());
    
    ll res = 0;
    vector<ll> sumq(n+1,0);
    rep(i,n){
        if(i) sumq[i] += sumq[i-1];
        M[i].second -= sumq[i];
        if(M[i].second<=0) continue;
        // 攻撃回数
        ll num = (M[i].second + (a-1) )/a;
        // 与える攻撃量
        ll q = a*num;
        res += num;
        // 攻撃範囲外になったら imos っぽく -=q する
        sumq[i+1] += q;
        sumq[upper_bound(X.begin(),X.end(),X[i]+2*d)-X.begin()] -= q;
    }
    cout << res << endl;
}

Measured memory_bytes: 10004
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <string.h>
#include <sstream>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using vec = vector<T>;
template<typename T> using prior = priority_queue<T>;

const ll MOD = 1e9+7;
const ll SPMOD = 998244353;
const double PI  = 3.14159265358;
const double EPS = 1e-8;
 
#define INT_MX 2147483647
#define INF ((int)1e9)
#define LLINF ((ll)1e18)
#define F first
#define S second
#define MP(x,y) make_pair(x,y)
#define siz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define Unique(v) v.rs(unique(ALL(v))-v.begin())
#define EB emplace_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define __ <<' '<<
#define kiyohime ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

// template
ll POW();
int gcd(int a, int b);
// end of template

#define N 110

void solve(){
    ll a, b;
    
    cin >> a >> b;
    cout << min(a % b, abs(b - a%b)) << '\n';
}

int main(){
    kiyohime
    int T = 1;
    
//    cin >> T;
    while(T--){
        solve();
    }
}


// templates

ll POW(ll a, ll b, ll m = MOD){
    ll res = 1;
    while(b){
        if(b&1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[500009],br[500009];
int main()
{
    ll a,b,c,i,j,k;
    string s,d;
    cin>>a>>b;
    if(a==b)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
}


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

double N,M,a,b;
long long res;
struct Drink{
    double A,B;
};
bool operator< (const Drink& d1,const Drink& d2){
    return d1.A>d2.A;
}

std::priority_queue<Drink> que;

int main(){

    std::cin>>N>>M;

    for(int i=0;i<N;i++){
    std::cin>>a>>b;
    que.push((Drink){a,b});
    }

    while(M){
        if(M-que.top().B>=0){
        res+=que.top().A*que.top().B;
        M-=que.top().B;
        }
        else{
        res+=M*que.top().A;
        M=0;
        }
        que.pop();
    }

    std::cout<<res<<std::endl;

    return 0;
}

Measured memory_bytes: 2420
#include<stdio.h>

int main(void)
{
	int i,S,T,s;
	
	S=0;
	T=0;
	for(i=0;i<=3;i++)
	{
		scanf("%d",&s);
		S+=s;
	}
	for(i=0;i<=3;i++)
	{
		scanf("%d",&s);
		T+=s;
	}
	if(S>=T) printf("%d\n",S);
	else printf("%d\n",T);
	return 0;
}

Measured memory_bytes: 592
#include<iostream>  
#include<vector>  
#include<algorithm>  
  
using namespace std;  
typedef long long ll;  
const int maxn = 2000 + 5;  
const ll oo = 0x3f3f3f3f3f3f3f3f;  
int N, M;  
ll d1, d2;  
  
int main()  
{  
    while (cin >> N >> M)  
    {  
        vector<int>a(M);  
        vector<int>b(M);  
        vector<ll>c(M);  
        for (int i = 0; i < M; i++)  
        {  
            cin >> a[i] >> b[i] >> c[i];  
            a[i]--, b[i]--;  
        }  
        vector<ll>d(N, -oo);  
        d[0] = 0LL;  
        for (int i = 0; i < 2 * N; i++)  
        {  
            for (int j = 0; j < M; j++)  
            {  
                d[b[j]] = max(d[b[j]], d[a[j]] + c[j]);  
            }  
            if (i == N - 1)  
                d1 = d[N - 1];  
            if (i == 2 * N - 1)  
                d2 = d[N - 1];  
        }  
        if (d1 == d2)  
            cout << d1 << endl;  
        else  
            cout << "inf" << endl;  
    }  
    return 0;  
}  



Measured memory_bytes: 888
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (__typeof(a) i = (a); i < (b); ++i)
#define iter(it, c) \
  for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const int INF = ~(1 << 31);

#define sc second
#define fs first
#define pb push_back
#define mp make_pair

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T>
T smod(T a, T b) {
  return (a % b + b) % b;
}
// vim: cc=60 ts=2 sts=2 sw=2:

typedef long double ld;

ld p[3010];

ld memo[3010][3010];
ld prob(int at, int num) {
  if (at == -1) {
    if (num == 0)
      return 1;
    else
      return 0;
  }
  if (num < 0) return 0;

  if (memo[at][num] >= -0.01) return memo[at][num];

  ld res = p[at] * prob(at - 1, num - 1) + ((ld)1 - p[at]) * prob(at - 1, num);
  return memo[at][num] = res;
}

int main() {
  // code
  memset(memo, -1, sizeof(memo));

  int n;
  cin >> n;

  rep(i, 0, n) cin >> p[i];

  cout << setprecision(11);
  ld res = 0;
  rep(i, n / 2 + 1, n + 1) { res += prob(n - 1, i); }

  cout << res << endl;

  // codend
}


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

int c(int h, int w, int k, vector<string> cc) {
  int res = 0;
  for(int i=0; i<(1<<h); i++) {
    for(int j=0; j<(1<<w);j++) {
      //cout << i << " " << j << endl;
      int count = 0;
      for(int a=0;a<h;a++) {
	for(int b =0;b<w;b++) {
	  //cout << a << " " << b << endl;
	  if( !(j & (1 << b)) && !(i & (1 << a)) && cc[a][b] == '#') {
	    count++;
	  }
	}
      }
      if(count ==k) {
	res++;
	//cout << " !! " << endl;
      }
    }
  }
  return res;
}

int main() {

  int h, w, k;
  cin >> h >> w >> k;
  vector<string> cc(h);
  for(int i=0;i<h;i++) {
      cin >> cc[i];
  }
  cout << c(h, w, k, cc);
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define INF 1.0e9
using namespace std;
typedef long long ll;

int n;
const int MAX_N = 1.0e5;
int v_even[MAX_N/2], v_odd[MAX_N/2];

vector<int> mode(int x[], int size) {
    map<int, int> mp;
    vector<int> cls_freq;
    for (int i = 0; i < 4; i++) cls_freq.push_back(0);
    for (int i = 0; i < size; i++) {
        mp[x[i]]++;
        if (cls_freq[1] < mp[x[i]]) {
            cls_freq[1] = mp[x[i]];
            cls_freq[0] = x[i];
        }
        else if (cls_freq[3] < mp[x[i]]) {
            cls_freq[3] = mp[x[i]];
            cls_freq[2] = x[i];
        }
    }
    return cls_freq;
}

int main() {
    cin >> n;
    for (int i = 0; i < n/2; i++) cin >> v_even[i] >> v_odd[i];
    vector<int> mode_even = mode(v_even, n/2);
    vector<int> mode_odd = mode(v_odd, n/2);
    int ans = 0;
    if (mode_even[0] != mode_odd[0]) {
        ans = n - mode_even[1] - mode_odd[1];
    }
    else {
        ans = min(n - mode_even[1] - mode_odd[3], n - mode_even[3] - mode_odd[1]); 
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2944
N = $stdin.gets.to_i
L = $stdin.gets.split.map {|i| i.to_i }
Lsort = L.sort.reverse
Llen = L.length

cnt = 0
0.upto(Llen - 3) do |i|
  li = Lsort[i]
  (i + 1).upto(Llen - 2) do |j|
    lj = Lsort[j]
    next if li == lj
    (j + 1).upto(Llen - 1) do |k|
      lk = Lsort[k]
      next if lj == lk
      break if li >= lj + lk
      cnt += 1
    end
  end
end
puts cnt


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


int main(){
    string S;
    cin >> S;
    int N = S.length();
    rep(i,N){
        if(S[i] != S[N-1-i]){
            cout << "No" << endl;
            return 0;
        }
    }
    rep(i,N/2){
        if(S[i] != S[N/2-1-i]){
            cout << "No" << endl;
            return 0;
        }
    }
    for(int i=N/2;i<N;i++){
        if(S[i] != S[N-1-i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
  ll n;
  cin >> n;
  ll t = n/3600;
  ll m = (n-3600*t)/60;
  ll s = n%60;
  cout << t << ':' << m << ':' << s << endl;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
int fx4[] = {1 , -1 , 0 , 0};
int fy4[] = {0 , 0 , 1 , -1};
int Kfx[]= {-2,-2,2,2,1,1,-1,-1}; ///knight move x - exis
int Kfy[]= {1,-1,1,-1,2,-2,2,-2}; ///knight move y- exis
int fx8[]= {1,1,1,0,0,-1,-1,-1};
int fy8[]= {0,1,-1,1,-1,0,1,-1};
#define ll long long int
#define pii pair<int,int>
#define llu unsigned long long
#define inf 1<<28
#define gama 0.57721566490
#define PI              acos(-1.0)
#define INF             0x7fffffff
#define MOD             1000000007
#define EPS             1e-7
#define all(r)(r).begin(),(r).end()
/*
bool status[mx];
void sieve(){
   long long int  i,j;
    for(i=2;i<=mx;i++)
    {
        status[i]=0;
    }
    for( i=2;i<=sqrt(mx);i++){
        if(status[i]==0)
        {
            for(j=i*i;j<=mx;j+=i){
                status[j]=1;
            }
        }
    }
}*/
ll BM( ll a , ll b , ll m )
{
    if ( b == 0 ) return 1 ;
    ll x = BM(a,b/2,m);
    x = (( x % m) * (x % m))%m;

    if( b % 2 ) x = (( x % m) * (a %m)) % m ;
    return x ;
}
#define dd double
#define sc scanf
#define pr printf
#define VI vector<int>
#define VS vector<string>
#define VC vector<char>
#define VLL vector<long long int>
#define FILE freopen("input.txt","rt",stdin); freopen("output.txt","w",stdout);
#define p_b push_back
#define mem(x,y) memset(x,y,sizeof(x))
#define F(i,a,b) for(i=a;i<=b;i++)
#define sc1(a) scanf("%d",&a)
#define scL1(a) scanf("%lld",&a)
#define scL2(a,b) scanf("%lld%lld",&a,&b)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define fori(N)          for(int i = 0; i<(N); i++)
#define forj(N)         for(int j = 0; j<(N); j++)
#define fork(N)         for(int k = 0; k<(N); k++)
#define forl(N)         for(int l = 0; l<(N); l++)
#define ford(N)         for(int d = 0; d<(N); d++)
#define fori1(N)          for(int i = 1; i<=(N); i++)
#define forj1(N)         for(int j = 1; j<=(N); j++)
#define fork1(N)         for(int k = 1; k<=(N); k++)
#define ford1(N)         for(int d = 1; d<=(N); d++)
#define sqr(x)           (x)*(x)
#define TEST int test,te=0;cin>>test;
#define segment_tree int l=(n*2),r=(n*2)+1,mid=(l+r)/2
#define Mx 100005
#define mx 10005

int main()
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);///Beware of use it, if u use it dont use scanf or printf
    int a,b,c;
    cin>>a>>b>>c;
    if(a+b+c>=22)cout<<"bust"<<endl;
    else cout<<"win"<<endl;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init));

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  while(cin >> n && n){
    ll x,y,h,w,res = 0,size;
    rep(i,n){
      cin >> x >> y >> h >> w;
      size = x+y+h;
      if(size <= 60 && w <= 2){
        res += 600;
      }
      else if(size <= 80 && w <= 5){
        res += 800;
      }
      else if(size <= 100 && w <= 10){
        res += 1000;
      }
      else if(size <= 120 && w <= 15){
        res += 1200;
      }
      else if(size <= 140 && w <= 20){
        res += 1400;
      }
      else if(size <= 160 && w <= 25){
        res += 1600;
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 3152
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, h, m; cin >> a >> b >> h >> m;
    double radh = 30.0 * h, radm = 6.0 * m;
    radh += 0.5 * m;
    double mid = abs(radh - radm);
    // chmin(mid, 360 - mid);
    double rad = mid * M_PI / 180.0;
    double c2 = (double)(a * a) + (double)(b * b) - (double)(2 * a * b) * cos(rad);
    cout << fixed << setprecision(12) << sqrt(c2) << '\n';
    return 0;
}


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

using namespace std;

int main()
{
  while(1){
    int N,M;
    double P;
    cin>>N;
    cin>>M;
    cin>>P;
    if(N == 0 && M == 0 && P == 0){
      break;
    }

    int sum = 0;
    vector<int> n;
    for(int i = 0;i < N;++i){
      int j = 0;
      cin>>j;
      n.push_back(j);
      sum += 100 * j;
    }

    int getter = n.at(M-1);
    sum = sum * (100-P) / 100;

    int ans;
    if(getter != 0){
      ans = sum / getter;
    }
    else{
      ans = 0;
    }
  
    cout<<ans<<endl;
  }

  return 0;
}


Measured memory_bytes: 3040
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#include <functional>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;

using namespace std;

#ifndef LOCAL
#define cerr _cer
struct _cert
{
    template <typename T> _cert& operator << (T) { return *this; }
};
_cert _cer;
#endif

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
        cerr << (*i) << " ";
    }
    cerr << "\n";
}
const int MAXN = 120000;

int n;
int p[MAXN];
set<int> eds[MAXN];
vector<pair<int, int >> go;


int get(int a) {
    if (a == p[a])
        return a;
    return p[a] = get(p[a]);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        p[i] = i;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a, --b;
        eds[a].insert(b);
        eds[b].insert(a);
    }
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a, --b;
        if (eds[a].count(b)) {
            go.push_back(make_pair(a, b));
        }
        else {
            eds[a].insert(b);
            eds[b].insert(a);
        }
    }
    int cnt = 0;
    while (!go.empty()) {
        ++cnt;
        int a, b;
        tie(a, b) = go.back();
        go.pop_back();
        a = get(a);
        b = get(b);
        if (a == b) {
            --cnt;
            continue;
        }
        if (eds[a].size() > eds[b].size())
            swap(a, b);
        p[a] = b;
        eds[b].erase(a);
        eds[a].erase(b);
        for (int u: eds[a]) {
            eds[u].erase(a);
            if (eds[u].count(b))
                go.push_back(make_pair(u, b));
            else
                eds[u].insert(b), eds[b].insert(u);
        }
        eds[a].clear();
    }
    if (cnt == n - 1)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}




Measured memory_bytes: 24960
n=int(input())
prime=[2]
no=3
mod1=[]
mod2=[2]
mod3=[]
mod4=[]
while len(mod1)<n and len(mod2)<n and len(mod3)<n and len(mod4)<n:
  for i in prime:
    if(no%i==0):
      no+=1
      break
  else:
    prime.append(no)
    if(no%5==1):
      mod1+=[no]
    elif(no%5==2):
      mod2+=[no]
    elif(no%5==3):
      mod3+=[no]
    elif(no%5==4):
      mod4+=[no]
    no+=1
if(len(mod1)==n):
  ans=mod1
elif(len(mod2)==n):
  ans=mod2
elif(len(mod3)==n):
  ans=mod3
elif(len(mod4)==n):
  ans=mod4
for i in ans:
  print(i,end=' ')

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

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

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 1152921504606846976

int main()
{
    string s; cin >> s;
    int n = s.size();
    int l = -1, r = -1;
    rep(i,n-1){
        if(s[i] == s[i+1]){
            l = i+1; r = i+2;
        }
    }
    for(int i = 1; i < n-1; i++){
        if(s[i-1] == s[i+1]){
            l = i; r = i+2;
        }
    }
    cout << l << ' ' << r << endl;   
}

Measured memory_bytes: 512
#!/usr/bin/env python
# coding: utf-8

# In[32]:


N = int(input())
a = list(map(int, input().split()))


# In[33]:


mylist4 = [1 if x%4 == 0 else 0 for x in a]
mylist2 = [1 if x%2 == 0 else 0 for x in a]
b4 = sum(mylist4)
b2 = sum(mylist2)-b4
b1 = N-b2-b4
if b2 == 0:
    if b1 <= b4+1:
        print("Yes")
    else:
        print("No")
else:
    if b1 <= b4:
        print("Yes")
    else:
        print("No")


# In[ ]:





# In[ ]:






Measured memory_bytes: 20064
#include<bits/stdc++.h>
using namespace std;
#define MAXN	5005
#define P	1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
long long n, k, dp[MAXN];
int tot, value[MAXN];
long long power(long long x, long long y) {
	if (y == 0) return 1;
	long long tmp = power(x, y / 2);
	if (y % 2 == 0) return tmp * tmp % P;
	else return tmp * tmp % P * x % P;
}
void inc(long long &x, long long y) {
	x = (x + y) % P;
}
void dec(long long &x, long long y) {
	x = (x - y + P) % P;
}
int main() {
	read(n), read(k);
	for (int i = 1; i * i <= n; i++) {
		if (i * i == n) value[++tot] = i;
		else if (n % i == 0) {
			value[++tot] = i;
			value[++tot] = n / i;
		}
	}
	sort(value + 1, value + tot + 1);
	for (int i = 1; i <= tot; i++) {
		dp[i] = power(k, (value[i] + 1) / 2);
		for (int j = 1; j < i; j++)
			if (value[i] % value[j] == 0) dec(dp[i], dp[j]);
	}
	long long ans = 0;
	for (int i = 1; i <= tot; i++)
		if (value[i] & 1) inc(ans, value[i] * dp[i] % P);
		else inc(ans, value[i] / 2 * dp[i] % P);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
p = [1]*300010
p[0]=p[1]=0
for i in range(2, 300010):
  if not(i%7==1 or i%7==6):
    p[i] = 0

for i in range(2, 300010):
  if p[i]:
    for j in range(i*2, 300010, i):
      p[j] = 0

doyososu = []
for i in range(2, 300010):
  if p[i]:
    doyososu.append(i)

while True:
  n = int(input())
  if n==1:
    break
  ans = []
  for e in doyososu:
    if n%e==0:
      ans.append(e)
  print(n, ":", sep="", end=" ")
  print(*ans)


Measured memory_bytes: 9248
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mm=1000000007;
const int n=10000000;

void solve()
{
	int a,b;
	cin>>a>>b;
	int a1[317];
	for(int i=0;i<317;i++)
	{
		a1[i]=(i+1)*(i+1);
	}
	int d=0;
	int c;
	if(b/10==0)
	{
		c=a*10+b;
	}
	else if(b/100==0)
	{
		c=a*100+b;
	}
	else
	{
		c=a*1000+b;
	}
	for(int i=0;i<317;i++)
	{
		if(c==a1[i])
		{
			cout<<"Yes\n";
			d=1;
			break;
		}
	}
	if(d==0)
	{
		cout<<"No\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	//int t; cin >> t; while(t--)
	solve();
	//cout << (solve() ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;


int main() {
  ll n; cin >> n;
  Vl l(n);
  rep(i, 0, n) cin >> l[i];

  sort(ALL(l));
  ll cnt = 0;
  rep(i, 0, n-2){
    rep(j, i+1, n-1){
      rep(k, j+1, n){
        if(l[i]+l[j]>l[k]) cnt++;
        else break;
      }
    }
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
import math
abcd= int(input())
a=math.floor(abcd/1000)
abcd = abcd - a*1000
b=math.floor(abcd/100)
isbad = False
if b==a:
    isbad = True

abcd = abcd - b*100
c=math.floor(abcd/10)
if c==b:
    isbad = True

d = abcd - c*10
if d==c:
    isbad = True

if isbad:
    print('Bad')
else:
    print('Good')
# print(a,b,c,d)



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

using namespace std;
int player(char ch){
  int ans = 0;
  if(ch=='a') ans = 1;
  else if(ch=='b') ans = 2;
  else if(ch=='c') ans = 3;
  return ans;
}
int main(){
	string A, B, C;
  	cin >> A >> B >> C;
  bool winner = false;
  int current = 1;
  string ans = "";
  while(!winner){
    char f = 0;
    if(current==1){
    	f=A[0];
      	current=player(f);
      if(A.length()>0)
      	A.erase(0,1);
      else{
        winner = true;
        ans += 'A';
      }
        
    }
    else if(current==2){
      	f=B[0];
      	current=player(f);
      if(B.length()>0)
      	B.erase(0,1);
      else{
        winner = true;
        ans += 'B';
      }
    }
    else if(current==3){
      	f=C[0];
      	current=player(f);
      if(C.length()>0)
      	C.erase(0,1);
      else{
        winner = true;
        ans+= 'C';
      }
    }
  }
  cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
dp = [[INF]*(2**N) for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(2**(ci-1) for ci in c)
    for j in range(2**N):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

print(dp[M][2**N-1] if dp[M][2**N-1] != INF else -1)


Measured memory_bytes: 76012
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <climits>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string.h>
#include <iomanip>
#include <ctype.h>

#define ll          long long int
#define ull         unsigned long long int
#define pb          push_back
#define pii         pair<int,int>
#define F         first
#define S          second
#define vi          vector<int>
#define vli          vector<ll>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define M_PI        3.14159265358979323846
#define mp          make_pair
#define sz(x)       (int)x.size()
#define hell        1000000007
#define matrix      vector<vector<ll>>
#define forn(i,a,b)  for(int i=a;i<b;i++)
#define eps 0.000000001
#define all(a)      (a).begin(),(a).end()
const long long INF = (long long) 1e7+1;
const long long mod = (long long) 15746;

using namespace std;
void solve();

void fastIO() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int main(){
   fastIO();
    solve();
}
//void sieve();
ll pw(ll k,ll x);
ll gcd(ll x,ll y);


/*class CompareDist
{
public:
    bool operator()(pair<ll,int> a,pair<ll,int> b) {
        if(a.F!=b.F)
        return a.F<b.F;
        else
        return a.S>b.S;
    }
};*/

void solve(){

  int test;
  //cin>>test;
  test=1;
  while(test--){
    ll n;
    cin>>n;
    cout<<(n-1)/2;
  }
}

/*bool issafe(int x,int y){
  return (x>=0 && y>=0 && x<n && y<m);
}*/

///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1

ll gcd(ll x,ll y){
  if(x==0)
  return y;
  else
  return gcd(y%x,x);
}


ll pw(ll k,ll x){
  if(x==0)
  return 1;
  if(x&1)
  return ((pw(k,x-1)%hell)*k%hell)%hell;
  else
  return ((pw(k,x/2)%hell)*(pw(k,x/2)%hell))%hell;
}

/*void sieve(){

  for(int i=2;i<=1000000;i++){
    if(prime[i]==true){
      for(int j=i*i;j<=1000000;j+=i)
      prime[j]=false;
    }
  }

}*/


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>

#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000001;

using namespace std;



int main(void) {
	int n, m;

	cin >> n >> m;
	vector<int>a(m + 1);
	vector<int>b(m + 1);
	vector<bool>dps(n + 1);
	vector<bool>dpe(n + 1);
	FOR(i, 1, n) {
		dps[i] = dpe[i] = false;
	}

	FOR(i, 1, m) {
		cin >> a[i] >> b[i];
		if (a[i] == 1) {
			dps[b[i]] = true;
		}
		if (b[i] == n) {
			dpe[a[i]] = true;
		}
	}
	FOR(i, 1, n) {
		if (dps[i] == 1 && dpe[i] == 1) {
			cout << "POSSIBLE" << endl;
			break;
		}
		if (i == n) {
			cout << "IMPOSSIBLE" << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
#define INF 1000000000
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repX(i, n ,x) for (int i = x; i < (int)(n); i++)
#define repM(i, n) for (int i = n; i > 0; i--)

int main() {
    int A,B;
    cin >> A >> B;
    repX(i,3+1,1){
        if(i!=A&&i!=B){
        cout << i << endl;
        return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
/*  
    tanuj_johal :: gla_clg_sync_with_CSE(true);
    bonding.tie(true);
    hardwork.tie(true);
    
    ::::::::--------------------::::::::
*/

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

using namespace std;
using namespace __gnu_pbds;

#define ll          long long
#define fio         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define vi          vector<ll>
#define pp          push_pop
#define pll         pair<ll,ll>
#define in          insert
#define f(i,a,b)    for(ll i=a;i<b;i++)
#define f0(i,n)     f(i,0,n)
#define arr(a,n)    int a[n];f0(i, n) cin >> a[i];
#define ini(a,n)    memset(a,n,sizeof(a))
#define ff          first
#define ss          second
#define inf         10000000000000000
#define all(p)      p.begin(), p.end()
#define que_max     priority_queue <int>
#define que_min     priority_queue <int, vi, greater<int>>
#define print(a)    for(auto i:a){cout<<i<<" ";}
#define print1(a)   for(auto i:a){cout<<i.ff<<" "<<i.ss<<endl;}

typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> Set;
unordered_map<ll,vi> g;
unordered_map<ll,ll> vis;

const ll mod = 1e9+7;

ll power(ll x,ll y,ll p){ll r=1;x=x%p;while(y>0){if(y&1)r=(r*x)%p;y=y>>1;x=(x*x)%p;}return r;}
const ll N = 1e5+10;


bool imp = false;
void solve()
{
    ll n;cin>>n;
    if(n%10==3){
        cout<<"bon";
    }
    else if(n%10 == 0 or n%10 == 8 or n%10 == 1 or n%10 == 6)
        cout<<"pon";
    else
        cout<<"hon";
}

int main()
{
    fio
    int t=1;
    if(imp) cin>>t;
    while(t--)
    {
        // cout<<"Case #"<<tc<<": ";
        g.clear();
        vis.clear();
        solve();
        // tc++;
    }
    
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    int a,b; cin>>a>>b;
    if(a+b<10) cout<<a+b<<endl;
    else cout<<"error"<<endl;
    }

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node {
	int key;
	Node parent, left, right;

	public Node(int key) {
		super();
		this.key = key;
	}

}

class Tree {
	Node root;



	void insert(Node z) {
		Node y = null; // parent of x
		Node x = this.root; // the root of Tree

		while (x != null) {
			y = x;
			if (z.key < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		z.parent = y;

		if (y == null) {
			this.root = z;
		} else {
			if (z.key < y.key) {
				y.left = z;
			} else {
				y.right = z;
			}
		}
	}

	boolean find(int key, Node currentNode) {
		if (currentNode == null) {
			return false;
		}
		if (currentNode.key == key) {
			return true;
		}
		if (currentNode.key > key) {
			return find(key, currentNode.left);
		} else {
			return find(key, currentNode.right);
		}
	}
}

public class Main {

	static StringBuilder sb;

	public static void printPreOrder(Node node) {
		if (node == null) {
			return;
		}

		sb.append(" " + node.key);
		printPreOrder(node.left);
		printPreOrder(node.right);
	}

	public static void printInOrder(Node node) {
		if (node == null) {
			return;
		}

		printInOrder(node.left);
		sb.append(" " + node.key);
		printInOrder(node.right);
	}



	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int m = Integer.parseInt(br.readLine());
		String[] operation;
		int key;
		Tree tree = new Tree();
		sb = new StringBuilder();

		for (int i = 0; i < m; i++) {
			operation = br.readLine().split(" ");
			if (operation[0].equals("insert")) {
				key = Integer.parseInt(operation[1]);
				tree.insert(new Node(key));
			} else if (operation[0].equals("find")) {
				key = Integer.parseInt(operation[1]);
				if (tree.find(key, tree.root)) {
					System.out.println("yes");
				} else {
					System.out.println("no");
				}
			} else {
				printInOrder(tree.root);
				sb.append("\n");
				printPreOrder(tree.root);
				System.out.println(sb.toString());
				sb.setLength(0);
			}
		}
	}
}


Measured memory_bytes: 139968
# -*- coding: utf-8 -*-


def gcd(x, y):
    if x < y:
        x, y = y, x

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


if __name__ == '__main__':

    x, y = map(int, input().split())
    print(gcd(x, y))



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

#define LEN 3
#define T 0
#define X 1
#define Y 2
#define X_NG 0
#define Y_NG 1
#define ALL_OK 2

int main(void){
    int N;
    cin >> N;
    int travelplan[N][LEN];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < LEN; j++){
            cin >> travelplan[i][j];
        } 
    }

    int location[LEN] ={0,0,0};
    int tmp = 0;
    bool possbleflg = false;
    int state = X_NG; 
    for(int i = 0; i < N; i++){
        for(int j = location[T]; j <= travelplan[i][T]; j++){
            possbleflg = false;
            switch(state){
                case X_NG:
                    tmp = travelplan[i][X] - location[X];
                    if(tmp == 0) {
                        state = Y_NG;
                    }
                    else if(tmp > 0){
                        location[X] += 1;
                        break;
                    }
                    else  if(tmp < 0){
                        location[X] -= 1;
                        break;   
                    }
                case Y_NG:
                    tmp = travelplan[i][Y] - location[Y];
                    if(tmp == 0) {
                        state = ALL_OK;
                    }
                    else if(tmp > 0){
                        location[Y] += 1;
                        break;
                    }
                    else  if(tmp < 0){
                        location[Y] -= 1;
                        break;   
                    }
                case ALL_OK:             
                    if(j != travelplan[i][T]){
                         location[Y] += 1;
                         state = Y_NG;
                    }else{
                        possbleflg = true;
                        location[T] = travelplan[i][T];
                        location[X] = travelplan[i][X];
                        location[Y] = travelplan[i][Y];
                    }
                default:
                    break;
            }
        }
        if(possbleflg == false) break;
        state = X_NG;
    }

    if(possbleflg == true){
      cout << "Yes" << endl;
    }else{
       cout << "No" << endl;       
    }

    return 0;
}


Measured memory_bytes: 1536
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

# import numpy as np


## test data
# 4
# 3 1 4 2
# 10 20 30 40
## ans=60

# import bisect

class BIT:

	def __init__(self,size):
		self.N = size
		self.bit = [0] * (self.N+1)

	def getSum(self,i):
		s = 0
		while 0 < i:
			s += self.bit[i]
			i -= i & -i

		return s

	def getMax(self,i):
		s = 0
		while 0 < i:
			s = max(s, self.bit[i])
			i -= i & -i

		return s

	def add(self,i,val):
		while i <= self.N:
			# for range summary query
			# self.bit[i] += val
			# for range maximum query
			self.bit[i] = max( self.bit[i], val )
			i += i & -i

def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = BIT(N)
	for n in range(N):
		tree.add( H[n], tree.getMax(H[n]) + A[n] )

	lis = tree.getMax(N)

	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()


Measured memory_bytes: 115164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, start, n) for (int i = (int)(start); i < (int)(n); ++i)
static const int INFTY = (1 << 30);
int N, M;
void func()
{
    cin>>N;
    string s[N];
    rep(i, 0, N) {
        cin>>s[i];
        sort(s[i].begin(), s[i].end());
    }
    sort(&s[0], &s[N]);
    ll ans=0;
    int i=0;
    while (i<N) {
        int j, k=1;
        for (j=i+1;s[i]==s[j];++j)++k;
        ans+=(ll)k*(ll)(k-1)/2;
        i=j;
    }
    cout<<ans<<endl;

}
int main()
{
    func();
}


Measured memory_bytes: 6772
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;

const int N=1000005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
inline void read(int &x){
	x=0;char ch=getchar(),rev=0;
	while(ch>'9'||ch<'0') rev=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=rev?-x:x;
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int r,c,n,u[N],s[N],top,val[N],now;
int sx,xx[N],sy,yy[N];
map<pii,int> vis,ck;

bool check(int x,int y){
	return !x||!y||x==r||y==c;
}
void ins(int x,int y){
	if(ck[mp(x,y)]) return;
	ck[mp(x,y)]=1;
	int k=vis[mp(x,y)];
	if(!k) return;
//	printf("%d %d\n",x,y);
	if(~u[k]&&u[k]!=now){puts("NO");exit(0);}
	now^=val[k];
	u[k]=now;
}

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	srand(time(0));
	scanf("%d%d%d",&r,&c,&n);
	for(int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(!check(x1,y1)||!check(x2,y2)) continue;
		val[i]=rand();
		vis[mp(x1,y1)]=i;
		vis[mp(x2,y2)]=i;
		xx[++sx]=x1;yy[++sy]=y1;
		xx[++sx]=x2;yy[++sy]=y2;
//		printf("%d %d %d %d\n",x1,y1,x2,y2);
		u[i]=-1;
	}
	sort(xx+1,xx+sx+1);
	sort(yy+1,yy+sy+1);
	sx=unique(xx+1,xx+sx+1)-xx-1;
	sy=unique(yy+1,yy+sy+1)-yy-1;
	for(int i=1;i<=sy;i++)
		ins(0,yy[i]);
	for(int i=1;i<=sx;i++) ins(xx[i],c);
	for(int i=sy;i;i--)ins(r,yy[i]);
	for(int i=sx;i;i--)ins(xx[i],0);
	puts("YES");
	return 0;
}

Measured memory_bytes: 61184
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
  int n,q;
  string s;
  cin>>n>>q>>s;
  vi memo(n);
  memo[0]=0;
  rep(i,n-1){
    if(s[i]=='A'&&s[i+1]=='C'){
      memo[i+1]=memo[i]+1;
    }
    else memo[i+1]=memo[i];
  }
  rep(i,q){
    ll ans =0;
    int l,r;
    cin>>l>>r;
    l--;r--; 
    ans+=memo[r]-memo[l];
    cout<<ans<<endl;
  }

}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <queue>
#include <cmath>
using namespace std;
typedef pair<string, string> P;

int main(int argc, char *argv[])
{
  int n, l;
  cin >> n;
  int min=pow(10,9);
  int max=0;
  for(int i=0;i<n;i++){
    cin >> l;
    if(max<l){
      max=l;
    }
    if(min>l){
      min=l;
    }
  }
  cout << max-min << endl;
  return 0;
}


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

using ll = long long;
using ull = unsigned long long;
#define countof(a) (sizeof(a)/sizeof((a)[0]))
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define bzero(p, n) memset(p, 0, n)
#define all(a) begin(a),end(a)
template<class T> inline void sort_uniq(T& c) { sort(ALL(c)); c.erase(unique(ALL(c)), c.end()); }
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
inline ll powll(ll x,ll y) {ll p=1; while(y--) p*=x; return p;}
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    ll N, M; cin >>N>>M;
    vector<pair<ll,ll>> AB(N);

    ll a, b;
    rep(i, N) {
        cin >> a >> b;
        AB[i] = make_pair(a, b);
    }
    sort(all(AB));

    ll ans = 0;
    ll buy, bought = 0;
    rep(i, N) {
        //cout << FMT2(AB[i].first, AB[i].second) << endl;
        buy = min(M - bought, AB[i].second);
        ans += AB[i].first * buy;
        bought += buy;
        if (bought == M)
            break;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792