akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> edge;
typedef pair<edge,int> state;

const int INF = 1e9;

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

  int n,t;
  cin >> n >> t;

  map<string, vector<int> > id;
  int v = 0;
  string A,B;
  cin >> A >> B;

  vector<string> name;
  vector< vector<int> > c(n);

  for(int i=0;i<n;i++){
    int a; cin >> a;
    for(int j=0;j<a;j++){
      string tmp;
      cin >> tmp;
      id[tmp].push_back(v+j);
      name.push_back(tmp);
    }
    for(int j=0;j<a-1;j++){
      int tmp;
      cin >> tmp;
      c[i].push_back(tmp);
    }
    v += a;
  }

  vector< vector<edge> > g(v);
  v = 0;
  for(int i=0;i<n;i++){
    for(int j=0;j<(int)c[i].size();j++){
      g[v].push_back(edge(c[i][j],v+1));
      g[v+1].push_back(edge(c[i][j],v));
      v++;
    }
    v++;
  }

  priority_queue<state,vector<state>,greater<state> > q;
  vector<edge> d(v,edge(INF,INF));
  for(int u : id[A]){
    q.push(state(edge(0,0),u));
    d[u] = edge(0,0);
  }
  set<string> use;

  while(q.size()){
    state s = q.top(); q.pop();
    int u = s.second;
    edge cost = s.first;
    if(d[u] < cost)continue;

    for(edge nxt : g[u]){
      edge nxtc = edge(nxt.first + cost.first, cost.second);
      int nxtu = nxt.second;
      if(d[nxtu] > nxtc){
	d[nxtu] = nxtc;
	q.push(state(nxtc,nxtu));
      }
    }

    if(use.count(name[u])==0){
      use.insert(name[u]);
      edge nxtc = edge(cost.first + t, cost.second + 1);
      for(int nxtu : id[name[u]]){
	if(d[nxtu] > nxtc){
	  d[nxtu] = nxtc;
	  q.push(state(nxtc,nxtu));
	}
      }
    }
  }


  edge ans = edge(INF,INF);
  for(int u : id[B]){
    ans = min(ans, d[u]);
  }

  if(ans == edge(INF,INF)) cout << -1 << endl;
  else cout << ans.first << " " << ans.second << endl;
}

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  int temp;
  if(a > b) swap(a,b);
  if(b > c) swap(b,c);
  if(a > b) swap(a,b);
  cout << a << " " << b << " " << c << endl;
}



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

typedef long long ll;

using namespace std;

int main(void) {
	// For fast IO
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	long double n, cur = 1, maxnum = 1000000000000000000;
	vector<long double> nums;
	cin >> n;
	
	for(int i = 0; i < n; i++) {
		long double num;
		cin >> num;
		if(num == 0) {
			cout << 0;
			return 0;
		}
		nums.push_back(num);
	}

	sort(nums.begin(), nums.end());

	for(int i = 0; i < n; i++) {
		if(nums[i] <= (maxnum / cur)) {
			cur *= nums[i];
		} else {
			cout << -1;
			return 0;
		}
	}
	
	cout << (long long)cur;

	return 0;
}

Measured memory_bytes: 5408
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int K;
  cin >> K;
  
 int i, j, k;
 int gcd1, gcd2;
 int sum = 0;
 for(i = 0; i < K; i++){
    for(j = 0; j < K; j++){
      for(k = 0; k < K; k++){
        gcd1 = std::__gcd(i + 1,j + 1);
        gcd2 = std::__gcd(gcd1, k + 1);
       sum += gcd2;
      }
    }
  }
  cout << sum << endl;
  return 0;
}


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

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

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

template<typename T1,typename T2>ostream& operator<<(ostream& os,const pair<T1,T2>& a) {os << "(" << a.first << ", " << a.second << ")";return os;}

const char newl = '\n';

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0;i < n;++i) cin >> a[i];
    map<int,ll> mp;
    for (int i = 0;i < n;++i) mp[a[i]]++;
    ll ans = 0;
    for (auto& p : mp) ans += p.second*(p.second-1)/2;
    for (int i = 0;i < n;++i) {
        cout << ans-mp[a[i]]+1 << newl;
    }
}

Measured memory_bytes: 10240
import java.io.*;
        import java.math.BigDecimal;
        import java.math.BigInteger;
        import java.util.*;

public class Main {
    static Input in = new Input(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int S = in.nextInt();
        int W = in.nextInt();
        if (S <= W)
            out.println("unsafe");
        else
            out.println("safe");
        out.flush();
    }

    static class Input {
        private BufferedReader br;
        private String[] buff;
        private int index = 0;

        Input(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return null;
        }
        String next() {
            while (buff == null || index >= buff.length) {
                buff = nextLine().split(" ");
                index = 0;
            }
            return buff[index++];
        }
        byte nextByte() {
            return Byte.parseByte(next());
        }
        short nextShort() {
            return Short.parseShort(next());
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        float nextFloat() {
            return Float.parseFloat(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
        BigDecimal nextBigDecimal() {
            return new BigDecimal(next());
        }
    }
}

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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>; 

#define INF 10000000000
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

//#define DEBUG

int main_(){
  int A,B,C;
  cin>>A>>B>>C;
  if(A==B&&B==C&&C==A)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
#ifdef DEBUG
  vector<string>test;
  /*
   * input for debug
   */
  for(int i=0;i<test.size();++i){
    stringbuf buf;
    streambuf*out=cout.rdbuf(&buf);
    cout<<test[i]<<flush;
    cout.rdbuf(out);
    streambuf*in=cin.rdbuf(&buf);
    main_();
    cin.rdbuf(in);
    cout<<endl;
  }
#else
  main_();
#endif

  return 0;
}


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

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

  using ldouble= long double;
  using coord= pair<ldouble, ldouble>;

  vector<coord> data(N);
  ldouble bufx, bufy;
  for(int i=0; i<N; i++){
    cin >> bufx >> bufy;
    data.at(i)= make_pair(bufx, bufy);
  }

  vector<vector<ldouble>> dists_by2(N, vector<ldouble>(N));
  vector<vector<coord>> midpoints(N, vector<coord>(N));
  vector<vector<coord>> normals(N, vector<coord>(N));
  for(int i=0; i<N; i++){
    for(int j= i+1; j<N; j++){
      auto [x_i, y_i]= data.at(i);
      auto [x_j, y_j]= data.at(j);

      ldouble x_m= (x_i+ x_j)/ 2.0L;
      ldouble y_m= (y_i+ y_j)/ 2.0L;
      ldouble dist= sqrt((x_j- x_i)*(x_j- x_i) + (y_j- y_i)*(y_j- y_i));

      dists_by2.at(i).at(j)= dist/ 2.0L;
      midpoints.at(i).at(j)= make_pair(x_m, y_m);
      normals.at(i).at(j)= make_pair(-(y_j- y_i)/dist, (x_j- x_i)/dist);
    }
  }

  constexpr ldouble eps= 1e-7;
  ldouble inc= sqrt(2.0L)* 500;
  ldouble exc= 0.0L;
  while(abs(inc- exc) > eps){
    ldouble mid= (inc+ exc)/ 2;

    auto is_inc= [&](ldouble mid){
      bool bool_mid= false;
      for(int i=0; i<N; i++){
        for(int j= i+1; j<N; j++){
          ldouble h= dists_by2.at(i).at(j);
          auto [x_m, y_m]= midpoints.at(i).at(j);
          auto [nx, ny]= normals.at(i).at(j);

          if(mid < h){ continue; }
          else{
            ldouble d_norm= sqrt(mid*mid - h*h);

            ldouble x_cand1= x_m+ d_norm* nx;
            ldouble y_cand1= y_m+ d_norm* ny;

            ldouble x_cand2= x_m- d_norm* nx;
            ldouble y_cand2= y_m- d_norm* ny;

            bool cand1= true;
            for(auto [x,y]:data){
              if((x- x_cand1)*(x- x_cand1)+ (y- y_cand1)*(y- y_cand1) > (mid+eps)*(mid+eps)){
                cand1= false;
                break;
              }
            }
            
            bool cand2= true;
            for(auto [x,y]:data){
              if((x- x_cand2)*(x- x_cand2)+ (y- y_cand2)*(y- y_cand2) > (mid+eps)*(mid+eps)){
                cand2= false;
                break;
              }
            }

            if(cand1 or cand2){
              bool_mid= true;
              break;
            }
          }
        }
        if(bool_mid){ break; }
      }

      return bool_mid;
    };

    if(is_inc(mid)){ inc= mid; }
    else           { exc= mid; }
  }
  
  cout << fixed;
  cout << setprecision(7) << inc << endl;
}

Measured memory_bytes: 4000
n = int(input())
a = list(map(int,input().split()))

for i in range(n):
    if(a[i] == 0):
        print(0)
        exit()

ans = 1
for i in range(n):
    ans = ans * a[i]
    if(ans > 1e18):
        print(-1)
        exit()

print(ans)

Measured memory_bytes: 88044
from sys import stdin

def main():

    input = stdin.readline

    N = int(input())
    A = list(map(int,input().split()))
    ans = [0] * N

    for i in range(N-1):
        ans[A[i]-1] += 1

    print('\n'.join(map(str,ans)))
    
if __name__ == "__main__":
    main()

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

// long long A[1000000];
long long N,X,Y;
long long K[40000];
int main(void)
{
    // freopen("aaa.in","r",stdin);
    scanf("%lld%lld%lld",&N,&X,&Y);
    for (long long i=1;i<N;i++)
    {
        for (long long j=i+1;j<=N;j++)
        {
            int kk=min(j-i,abs(i-X)+abs(j-Y)+1);
            K[kk]++;
        }
    }
    for (int i=1;i<N;i++) printf("%lld\n",K[i]);
    return 0;
}

Measured memory_bytes: 3216
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
typedef long long ll;
const ll INF = (ll)1e18;
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};
struct State {
  int pos;
  ll cost;
  State(int p, ll c) : pos(p), cost(c) {}
  bool operator <(const State &other) const {
    return cost > other.cost;
  }
};
vector<ll> shortest_path(const vector<vector<Edge>> &G, int s) {
  vector<ll> d(G.size(), INF);
  priority_queue<State> Q;
  Q.emplace(s, 0);
  while(!Q.empty()) {
    State cur = Q.top(); Q.pop();
    if(d[cur.pos] > cur.cost) {
      d[cur.pos] = cur.cost;
      for(const Edge &e : G[cur.pos]) {
        Q.emplace(e.to, cur.cost + e.cost);
      }
    }
  }
  return d;
}
struct BIT {
  int N;
  vector<vector<int>> data;
  BIT(int n) : N(n), data(n + 1) {}
  void append(int a, int w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x].push_back(w);
    }
  }
  void setup() {
    for(int a = 1; a <= N; ++a) sort(data[a].begin(), data[a].end());
  }
  int moreEq(int a, int w) {
    // index < a && value >= w
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x].end() - lower_bound(data[x].begin(), data[x].end(), w);
    }
    return ret;
  }
};
int main() {
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<vector<Edge>> G(N);
  REP(i, M) {
    int a, b, c; cin >> a >> b >> c;
    G[a].emplace_back(a, b, c);
    G[b].emplace_back(b, a, c);
  }
  int Q; cin >> Q;
  vector<ll> fs(Q), fg(Q);
  REP(i, Q) cin >> fs[i] >> fg[i];
  vector<ll> ds = shortest_path(G, 0);
  vector<ll> dg = shortest_path(G, N - 1);
  set<ll> values;
  REP(i, Q) {
    values.insert(fs[i]);
    values.insert(fg[i]);
  }
  REP(i, N) {
    values.insert(ds[i]);
    values.insert(dg[i]);
  }
  map<ll, int> cmp;
  int index = 0;
  for(ll i : values) cmp[i] = index++;
  BIT bit(values.size()+1);
  REP(i, N) bit.append(cmp[ds[i]], cmp[dg[i]]);
  bit.setup();
  REP(q, Q) {
    cout << bit.moreEq(cmp[fs[q]] + 1, cmp[fg[q]]) << endl;
  }
}

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

int main(){
  ll h,w;
  cin>>h>>w;
  ll odd = (w+1)/2,even = w - odd;
  if (h==1 || w == 1){
    cout << 1 << endl;
  }
  else {
    cout << odd * ((h+1)/2) + even * (h/2) << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll INF = 1LL << 62;
const int inf = 1 << 30;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    cout << "ABC" << n << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> h(n);
  for(int i=0;i<n;++i) cin>>h[i];
  int x,count,sum=0;
  int ans=0;
  while(ans<n){
    count=0;
    x=0;
    ans=0;
    for(int i=0;i<n;++i){
      if(x==0 && h[i]>0) ++count;
      x=h[i];
      if(h[i]>0) --h[i];
      else ans++;
    }
    sum+=count;
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 3572
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
    int a,b,C;
    cin>>a>>b>>C;
    double S,L,h,z;
    z=(acos(-1)/180)*C;
    S=a*b*sin(z)/2;
    L=sqrt(a*a+b*b-2*a*b*cos(z))+a+b;
    h=b*sin(z);
    printf("%f %f %f\n ",S,L,h);
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int sum = 0;
  
  for (int i = 0; i < N; i++){
    int l,r;
    cin >> l>>r;
    sum = sum + (r-l+1);

  }
  cout << sum <<endl;
}



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

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	ll N, A, B;

	cin >> N >> A >> B;
	cout << A * (N / (A + B)) + min(A, N % (A + B)) << endl;

	return 0;
}


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

using namespace std;

bool tik;
int n, sk, nelyg, kart, lyg;

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &sk);
        if (sk % 2 > 0) nelyg++;
        else if (sk % 4 == 0) kart++;
        else lyg++;
    }
    tik = false;
    if (nelyg <= kart) tik = true;
    else if (nelyg == kart + 1 && lyg == 0) tik = true;

    if (tik) printf("Yes\n");
    else printf("No\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define pb push_back

using namespace std;
using ll = long long int;
ll mpow(ll a, ll n, ll m = 1000000007)
{
	ll r = 1;
	while (n)
	{
		if (n & 1) r = r*a % m;
		a = a*a % m;
		n >>= 1;
	}
	return r;
}

using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
#define trav(a, x) for(auto &a : x)
#define rep(i, a, b) for(int i = (a); i < (b); ++i)

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

	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	ll n, d,a ; cin >> n >> d >> a;
	vector<array<ll, 2>> v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i][0] >> v[i][1];
	}
	sort(v.begin(), v.end());
	priority_queue<array<ll, 2>> pq;
	ll cur = 0, ans = 0;
	for (int i = 0; i < n; ++i)
	{
		while (!pq.empty())
		{
			auto u = pq.top();
			if (-u[0] >= v[i][0]) break;
			cur -= u[1];
			pq.pop();
		}
		v[i][1] -= cur;
		if (v[i][1] > 0)
		{
			ans += (v[i][1] + a - 1) / a;
			cur += a * ((v[i][1] + a - 1) / a);
			pq.push({-v[i][0] - 2LL*d, a * ((v[i][1] + a - 1) / a)});
		}
	}
	cout << ans;
}

Measured memory_bytes: 5620
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
 
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
 
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
 
// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
 
// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;
 
ll n;
ll a[5];
 
int main(){
  cin>>n;
  REP(i,5)cin>>a[i];
  ll v = *min_element(a,a+5);
  ll t = (n+v-1)/v;
  cout<<(t+4)<<endl;
  return 0;
}


Measured memory_bytes: 384
#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)
ll gcd(ll a,ll b){
  if(b==0) return a;
  return gcd(b,a%b);
}
ll lcm(ll a,ll b){
  return a*b/gcd(a,b);
}
template<typename T> inline bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }
const int MOD = 1e9+7;

int main() {
  int n;
  cin >> n;
  int p[9];
  int q[9];
  rep1(i,n)cin >> p[i];
  rep1(i,n)cin >> q[i];
  int a[9];
  a[0]=1;
  rep1(i,n-1)a[i]=a[i-1]*i;
  int A=1;
  rep1(i,n-1){
    int c=0;
    rep1(j,i){
      if(p[j]<p[i])c++;
    }
    A +=(p[i]-1-c)*a[n-i];
  }
  int B=1;
  rep1(i,n-1){
    int c=0;
    rep1(j,i){
      if(q[j]<q[i])c++;
    }
    B +=(q[i]-1-c)*a[n-i];
  }
  cout << abs(A-B);
}

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

int main()
{
    int N, X, Y;
    std::cin >> N >> X >> Y;
    // |-------------------+--------------+----------------|
    //                     +--------------+
    //   i           j                                           : j-i
    //                i      j                                   : min(j-i, |X-i|+|Y-j|+1)
    //                         i       j                         : min(j-i, |X-i|+|Y-j|+1)
    //                         i                j                : min(j-i, |X-i|+|Y-j|+1)
    //                                              i  j         : j-i
    // forall i,j. count[d(i, j)]に1足す
    // count[k]
    std::vector<int> count(N);
    for (int i = 1; i <= N; i++)
    {
        for (int j = i + 1; j <= N; j++)
        {
            int d = std::min(j - i, std::abs(X - i) + std::abs(Y - j) + 1);
            count[d]++;
        }
    }
    for (int k = 1; k <= N - 1; k++)
    {
        std::cout << count[k] << std::endl;
    }
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
vector<int>v[2003];
int dis[2003];
int vis[2003];
void solve(){
    int n,x,y;
    cin>>n>>x>>y;
    for(int i=1;i<n;i++){
        v[i].pb(i+1);
        v[i+1].pb(i);
    }
    v[x].pb(y);
    v[y].pb(x);
    for(int i=1;i<=n;i++){
        vis[i] = i;
        queue<pair<int,int> >q;
        q.push({i,0});
        while(!q.empty()){
            pair<int,int> p = q.front();
            int x = p.first;
            int h = p.second;
            dis[h]++;
            q.pop();
            for(int y : v[x]){
                if(vis[y]==i)continue;
                q.push({y,h+1});
                vis[y] = i;
            }
        }
    }
    for(int i=1;i<=n-1;i++)cout<<dis[i]/2<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
//	cin>> t;
	while(t--)solve();
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lld;
#define sq(x) x*x
#define fr(i,m,n) for(i=m;i<n;i++)
#define vec vector<int>
#define sint set<int>
#define qint queue<int>
#define mip map<int,int>
#define pint priority_queue<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define full(v) v.begin(),v.end()

int main()
{
    int i,j,k,a,b,c,x,y,z,n,m,t;
    string s,u,v;
    cin>>s;
    if(s=="ARC") cout<<"ABC"<<endl;
    else cout<<"ARC"<<endl;

}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
typedef long long ll;

struct Seg{
  typedef ll T;
  const T e = 0;
  void merge(const T &a, const T &b, T &c){
    c = max(a, b);
  }

  int n;
  vector<T> d;

  void init(int m){
    n = 1<<(32-__builtin_clz(m-1));
    d = vector<T>(2*n, e);
  }
  void init(vector<T> &v){
    init(v.size());
    FOR(j, 0, v.size()) d[j+n] = v[j];
    for(int k=n-1;k>0;k--) merge(d[k*2], d[k*2+1], d[k]);
  }
  void update(int k, T a){
    k+=n;
    d[k]=a;
    while(k){
      k >>= 1;
      merge(d[k*2], d[k*2+1], d[k]);
    }
  }
  T query(int L, int R) {
    L += n; R += n;
    T l=e, r=e;
    while (L < R) {
      if (L & 1) merge(l, d[L++], l);
      if (R & 1) merge(d[--R], r, r);
      L >>= 1; R >>= 1;
    }
    merge(l, r, l);
    return l;
  }
  T get(int a){
    return d[n+a];
  }
} seg;
const int N = 2e5;
int n, h[N];
ll a[N];

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  seg.init(n+1);
  FOR(i, 0, n) cin >> h[i];
  FOR(i, 0, n) cin >> a[i];
  ll ans = 0;
  FOR(i, 0, n){
    ll t = seg.query(0, h[i]) + a[i];
    ans = max(ans, t);
    seg.update(h[i], t);
  }
  cout << ans << endl;
}

Measured memory_bytes: 6656
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cctype>

int main(){

    std::string w;
    std::vector<std::string> t;
    std::cin >> w;

    while(true){
        std::string s;
        std::cin >> s;

        if(s == "END_OF_TEXT") break;

        std::transform(s.begin(), s.end(), s.begin(), ::tolower);

        t.emplace_back(s);
    }

    std::cout << std::count(t.begin(), t.end(), w) << std::endl;

    return 0;
}



Measured memory_bytes: 3168
ans = r = g = b = rg = gb = br = 0

n = int(input())
s = input()

for ch in s:
    if ch == 'R':
        r += 1
        br += b
        rg += g
        ans += gb

    if ch == 'B':
        b += 1
        br += r
        gb += g
        ans += rg

    if ch == 'G':
        g += 1
        rg += r
        gb += b
        ans += br

c = 0

for i in range(1, n // 2 + 1):
    for j in range(0, n - 1):

        if j + 2 * i >= n:
            break

        ch1 = s[j]
        ch2 = s[j + i]
        ch3 = s[j + 2 * i]

        if len({ch1, ch2, ch3}) == 3:
            c += 1

print (ans - c)



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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> v(m);
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int a;
      cin >> a;
      v[a - 1]++;
    }
  }
  int r = 0;
  for (auto e : v) {
    r += e == n;
  }
  cout << r << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace contest_Csharp
{

    class Program
    {
        public static (long m, long s)[,] dp;
        public static long mod;
        
        static void Main(string[] args)
        {
            checked
            {
                var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
                Console.SetOut(sw);

                var vals = Console.ReadLine().Split(' ').
                    Select(x => int.Parse(x)).ToList();


                var N = vals[0];
                var M = vals[1];
                //var S = vals[2];
                var parent = new int[N + 1];
                var treesize = new int[N + 1];
                int root(int n)
                {
                    if (parent[n] == n)
                        return n;
                    else
                        return root(parent[n]);
                }
                for (int i = 0; i < N+1; i++)
                {
                    parent[i] = i;
                    treesize[i] = 1;
                }
                //読み込み
                for (int i = 0; i < M; i++)
                {
                    var v = Console.ReadLine().Split(' ').
                    Select(x => int.Parse(x)).ToList();
                    var A = v[0];
                    var B = v[1];
                    var RA = root(A);
                    var RB = root(B);
                    if (RA != RB) {
                        if (treesize[RA] >= treesize[RB])
                        {
                            parent[RB] = RA;
                            treesize[RA] += treesize[RB];
                        }
                        else
                        {
                            parent[RA] = RB;
                            treesize[RB] += treesize[RA];
                        }
                    }
                }
                

                var ans = treesize.Max();

                
                
                Console.WriteLine(ans);

                Console.Out.Flush();
            }




        }
    }

}




Measured memory_bytes: 42944
def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

n,k = inp
a = inp
max = a.max
tab = na(max+1,0)
ans = 0
sans = 0
a.size.times do |i|
  a.size.times do |j|
    d1,d2 = a[i],a[j]
    if(d1 < d2)
      ans += 1
      sans += 1 if(i > j)
    end
  end
end
mans = sans + ans*(k-1)
if(k == 1)
  p sans
  exit
end

p ans = ((mans + sans)*k/2)%(10**9+7)

Measured memory_bytes: 1916
import java.util.*;

public class Main {
	final int MOD = 100000000;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	final int LEN = 100000;
	Scanner sc = new Scanner(System.in);


	void doIt() {
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		int dp[][] = new int[s.length + 1][t.length + 1];
		for(int i = 1; i <= s.length; i++) {
			for(int j = 1; j <= t.length; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if(s[i - 1] == t[j - 1]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);	
				}
			}
		}
		
		StringBuilder strb = new StringBuilder();
		int si = s.length, ti = t.length;
		while(si > 0 && ti > 0) {
			if(dp[si][ti] == dp[si - 1][ti]) {
				si--;
			}
			else if(dp[si][ti] == dp[si][ti - 1]) {
				ti--;
			}
			else {
				strb.append(s[si - 1]);
				si--;
				ti--;
			}
			//System.out.println(si + " " + ti);
		}
		System.out.println(strb.reverse().toString());
		/*
		for(int i = 0; i <= s.length; i++) {
			System.out.println(Arrays.toString(dp[i]));
		}
		*/
	}
	public static void main(String[] args) {
		new Main().doIt();
	}
}

Measured memory_bytes: 83148
fun main(args: Array<String>) {
  val s = readLine()!!
  val n = s.length
  for (i in 0 until n - 1) {
    if (s[i] == s[i + 1]) {
      println("${i + 1} ${i + 2}")
      return
    }
  }
  for (i in 0 until n - 2) {
    if (s[i] == s[i + 2]) {
      println("${i + 1} ${i + 3}")
      return
    }
  }
  println("-1 -1")
}


Measured memory_bytes: 34352
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int m, n;
double p[16][16], a[16][1 << 16];
double rec(int c, int bit){
	if(c >= n) return 1;
	if(bit == 0) return 0;
	
	double &res = a[c][bit];
	if(res >= 0) return res;
	res = 0;
	rep(i, m) if(bit & 1 << i){
		double t = 1, sum = 0;
		for(int j = c; j < n; j++){
			sum += t * (1 - p[i][j]) * rec(j, bit ^ 1 << i);
			t *= p[i][j];
		}
		sum += t;
		res = max(res, sum);
	}
	return res;
}

int main(){
	cin >> m >> n;
	rep(i, m) rep(j, n) cin >> p[i][j];
	rep(i, n) rep(j, 1 << m) a[i][j] = -1;
	printf("%.9f\n", rec(0, (1 << m) - 1));
	return 0;
}

Measured memory_bytes: 9440
// g++ -std=c++14

//Difficulty according to solve count during contest:
//A B C D H F E I G K L M N P S O Q R J U Z Y X T V W

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

#define int long long
const int mod = 1e9 + 7;

int n;
vector<vector<int> > child;
vector<vector<int> > dp;

void func(int node, int par){
  for(auto &x: child[node]){
    if(x != par)
      func(x, node);
  }
  dp[node][0] = 1;
  dp[node][1] = 1;
  for(auto &x: child[node]){
    if(x != par){
      dp[node][0] *= dp[x][1];
      dp[node][1] *= (dp[x][0] + dp[x][1]);
      dp[node][0] %= mod;
      dp[node][1] %= mod;
    }
  }
}


int32_t main(){
  cin >> n;
  child.resize(n + 1);
  dp.resize(n + 1, vector<int>(2, 0));
  for(int i = 0; i < n - 1; i++){
    int x, y;
    cin >> x >> y;
    child[x].push_back(y);
    child[y].push_back(x);
  }
  func(1, -1);
  cout << (dp[1][0] + dp[1][1]) % mod << endl;
}


Measured memory_bytes: 18152
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c=1;
  int date[100000]={};
  cin>>a;
  date[a]++;
  while(true){
    c++;
    if(a%2==0){
      date[a/2]++;
      a/=2;
    }
    else{
      date[(a*3)+1]++;
      a=(a*3)+1;
    }
    if(date[a]==2){
      b=c;
      break;
    }
  }
  cout<<b<<"\n";
}

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

int main() {
  string s,t; cin>>s>>t;
  vector<int> vs(26,0), vt(26,0);
  
  rep(i,s.size()){
    int x;
    rep(j,26){
      if(s[i]==alphabet[j]){x=j; break;}
    }
    vs[x]++;
  }
  sort(vs.begin(), vs.end());
 
  rep(i,t.size()){
    int x;
    rep(j,26){
      if(t[i]==alphabet[j]){x=j; break;}
    }
    vt[x]++;
  }
  sort(vt.begin(), vt.end());
  if(vs==vt){cout<<"Yes";}
  else{cout<<"No";}
}




Measured memory_bytes: 3808
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC145C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = Cin.Int();
            int[] X = new int[N];
            int[] Y = new int[N];
            for (int i = 0; i < N; i++)
            {
                var xy = Cin.IArr();
                X[i] = xy[0];
                Y[i] = xy[1];
            }

            var solver = new Solver(N, X, Y);
            Console.WriteLine(solver.Solve());
        }
    }

    class Solver
    {
        public int N;
        public int[] X;
        public int[] Y;

        public Solver(int n, int[] x, int[] y)
        {
            N = n;
            X = x;
            Y = y;
        }

        public IConvertible Solve()
        {
            double sum = 0;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    sum += Math.Sqrt((X[j] - X[i]) * (X[j] - X[i]) + (Y[j] - Y[i]) * (Y[j] - Y[i])) / N;
                }
            }

            return sum;
        }
    }

    internal static class Cin
    {
        public static string String()
        {
            return Console.ReadLine();
        }

        public static int Int()
        {
            return int.Parse(String());
        }

        public static int[] IArr()
        {
            return Split().Select(int.Parse).ToArray();
        }

        public static long Long()
        {
            return long.Parse(String());
        }

        public static long[] LArr()
        {
            return Split().Select(long.Parse).ToArray();
        }

        public static double Double()
        {
            return double.Parse(String());
        }

        public static double[] DArr()
        {
            return Split().Select(double.Parse).ToArray();
        }

        private static IEnumerable<String> Split()
        {
            return String().Split(' ');
        }
    }
}

Measured memory_bytes: 13268
#include<stdio.h>

int main(void)
{
   int n, i, a=0, w=0, t=0, r=0;
   char s[100000][4];

   scanf("%d",&n);
   for(i=0;i<n;i++)
      scanf("%s",&s[i]);

   for(i=0;i<n;i++){
      if(s[i][0]=='A')
         a++;
      else if(s[i][0]=='W')
         w++;
      else if(s[i][0]=='T')
         t++;
      else
         r++;
   }

   printf("AC x %d\n",a);
   printf("WA x %d\n",w);
   printf("TLE x %d\n",t);
   printf("RE x %d\n",r);
   return 0;
}

Measured memory_bytes: 2096
#include <bits/stdc++.h>
using namespace std;
constexpr uint64_t mod = 1e9 + 7;

int64_t calc(const vector<int> &x) {
  int64_t ans = 0;
  for (size_t i = 1; i <= x.size() - 1; ++i) {
    int w = x[i] - x[i - 1];
    ans = (ans + w * i * (x.size() - i)) % mod;
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<int> x(n), y(m);
  for (auto &e : x)
    cin >> e;
  for (auto &e : y)
    cin >> e;
  cout << (calc(x) * calc(y)) % mod << "\n";
}


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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		int n = Integer.parseInt(br.readLine());

		int[] input = new int[n];


		for(int i = 0; i < n; i++){
			input[i] = Integer.parseInt(br.readLine());
		}


		//先頭が0以外は論外
		if(input[0] != 0){
			System.out.println(-1);
			return;
		}
		//まずは可能かどうかの判定
		//長さが1ならA1も0でなければならない
		if(n == 1){
			if(input[0] == 0){
				System.out.println(0);
				return;
			}
			else {
				System.out.println(-1);
				return;
			}
		}

		//先頭が0で次が2以上は論外
		if(input[0] == 0 && input[1] >= 2){
			System.out.println(-1);
			return;
		}

		for(int i = 0; i < n - 1; i++){
			if(input[i] + 1 < input[i + 1]){
				System.out.println(-1);
				return;
			}
		}

		long sum = input[n - 1];
		long minus = 0;
		long result = 0;

		for(int i = n - 1; i > 0; i--){

//			if(input[i] >= 1){
//				result += input[i];
//				input[i - 1] -= input[i] - 1;
//			}

			sum += input[i - 1];
			if(input[i - 1] + 1 == input[i]){
				minus += input[i - 1];
			}
//			System.out.println("i = "+ i + " input[i] = "+input[i]);
		}
		result = sum - minus;

		System.out.println(result);
	}
}


Measured memory_bytes: 38900
/*
  Compete against Yourself.
  Author - Aryan Choudhary (@aryanc403)
*/

#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

clock_t time_p=clock();
void aryanc403()
{
#ifdef ARYANC403
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
#endif
}

#ifdef ARYANC403
#include "/home/aryan/codes/PastCodes/header.h"
#else
    #define dbg(args...)
#endif

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const pair<lli,string> &a,const pair<lli,string> &b)
{
    return a.X>b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    map<string,lli> m;
    string s;
    vector<pair<lli,string>> a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    cin>>n;

    fo(i,n)
    {
        cin>>s;
        m[s]++;
    }

    for(auto x:m)
        a.pb({x.Y,x.X});
    
    sort(all(a),cmp);
    for(auto x:a)
    {
        if(x.X==a[0].X)
            cout<<x.Y<<endl;
    }

}   aryanc403();
    return 0;
}


Measured memory_bytes: 29548
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 5010;

typedef bitset<N> BS;

int n, k, ans;
int a[N];

void dc(int l, int r, const BS& bs) {
  if (l == r) {
    if (a[l] < k) {
      bool f = true;
      for (int j = k - a[l]; j < k; ++j)
        f &= !bs[j];
      ans += f;
    }
    return;
  }
  int mid = (l + r) >> 1;
  BS rs = bs;
  for (int i = r; i > mid; --i)
    if (a[i] <= k)
      rs |= rs << a[i];
  dc(l, mid, rs);
  BS ls = bs;
  for (int i = l; i <= mid; ++i)
    if (a[i] <= k)
      ls |= ls << a[i];
  dc(mid + 1, r, ls);
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  BS bs;
  bs.set(0);
  dc(1, n, bs);
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


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

int main() {

    int N;
    cin >> N;

    vector<int> A(N), B(N), C(N-1);
    int sum = 0;

    rep(i, N) cin >> A[i];
    rep(i, N) {
        cin >> B[i];
        sum += B[i];
    }
    rep(i, N-1) cin >> C[i];

    rep(i, N-1) {
        if (A[i+1] - A[i] == 1) sum += C[A[i]-1];

    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
import core.stdc.stdio;
import std.algorithm;
import std.stdio;

int lowerBound(int[] data,int t){
	int l=0;
	int r=cast(int)data.length+1;
	while(r-l>1){
		int m=(l+r)/2;
		if(data[m-1]<t)
			l=m;
		else
			r=m;
	}
	return l;
}

void main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int[] u = new int[n];
	int[] k = new int[n];
	foreach(i;0..m){
		scanf("%d",&u[i]);
		int j;
		scanf("%d",&j);
		k[--j]=u[i];
	}
	foreach(i;m..n)
		scanf("%d",&u[i]);
	sort(u);
	int[] d=new int[n*2];
	static immutable int inf = 114514;
	bool Solve(int t){
		int c=n-u.lowerBound(t);
		foreach(i;0..n)
			if(k[i])
				if(k[i]>=t){
					d[i]=0;
					c--;
				}else
					d[i]=inf;
			else
				d[i]=1;
		int b=0,e=n;
		while(b<e-1){
			d[e++]=min(inf,d[b]+d[b+1]+d[b+2]-max(d[b],d[b+1],d[b+2]));
			b+=3;
		}
		return d[e-1]<=c;
	}
	int l=0,r=n;
	while(r-l>1){
		int s=(r+l)/2;
		if(Solve(u[s]))
			l=s;
		else
			r=s;
	}
	printf("%d\n",u[l]);
}

Measured memory_bytes: 3880
#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

const int N = 1e6 + 5;

int ans[N];
void solve() {
    for (int i=0;i<N;++i) ans[i] = 0;
    for (int i=1;i<N;++i) {
        for (int j=i;j<N;j+=i) {
            ans[j]++;
        }
    }
    int n;
    cin >> n;
    LL res = 0;
    for (int i=1;i<n;++i) res += ans[i];
    cout << res << '\n';
}

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

Measured memory_bytes: 7544
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;


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

string s;
cin>>s;
for(int i=0;i<s.size();i++) {
    if(s[i]=='?') s[i]='D';
}
cout<<s;


return 0;

}


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

#define M 1000007
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1 + (key % 999999); }

int find(char str[]){
  long long key;
  int h;
  int i;
  key = getKey(str);
  for(i = 0 ;; i++){
    h = (h1(key) + (i * h2(key))) % M;
    if(strcmp(H[h],str) == 0) return 1;
    else if(strlen(H[h])== 0 )return 0; //なにも見付からなかった時
      }
  return 0;
}

int insert(char str[]){
  long long key;
  int i=0,h;
  
  key = getKey(str);
  
  while(1){
    h = (h1(key) + (i * h2(key)))% M;
    if(H[h][0] == '\0' ) {
      strcpy(H[h],str);
      break;
    }
    else i++;
  }
}

int main(){
  int i, n, h;
  char str[L], com[9];
  for ( i = 0; i < M; i++ ) H[i][0] = '\0'; //what is it ? もしかして一文字目はNULL?
    
  scanf("%d", &n);
    
  for ( i = 0; i < n; i++ ){
    scanf(" %s %s", com, str);
    
    if ( com[0] == 'i' ){
      insert(str);
    } else {
      if (find(str)){
	printf("yes\n");
      } else {
	printf("no\n");
      }
    }
  }

  return 0;
}

Measured memory_bytes: 14280
w1 = input()
length = len(w1)
num_list = [-1]*(length+1)
c1 = 0
c2 = 0
for i in range(length):
    if i==0 and w1[i] == "<":
        num_list[0] = 0
    if i==(length-1) and w1[i] == ">":
        num_list[length] = 0
    if not i==length-1:
        if w1[i] == ">" and w1[i+1] =="<":
            num_list[i+1] = 0

    if(w1[i] == "<"):
        num_list[i+1] = num_list[i] + 1

for i in range(length-1,-1,-1):
    if (w1[i] == ">"):
        if(num_list[i] < num_list[i+1] + 1):
            num_list[i] = num_list[i+1] + 1


print(sum(num_list))

#0<3>2>1>0<1<2>0<1<2<3<4<5>2>1>0<1

#0<>>>0<<>0<<<<<>>>0<

Measured memory_bytes: 23336
#include <stdio.h>

int N, P, A[50];
int i,j,k;
long long ans;

int main(void){
scanf("%d %d",&N,&P);
k=0;
for(i=0;i<N-1;i++){
scanf("%d",&A[i]);
if(A[i]%2==1) {k=1;}
}

if(k==0){
if(P==1){printf("0"); return 0;}
ans=1;
for(i=0;i<N;i++){ans*=2;}
printf("%ld",ans);
return 0;
}

ans=1;
for(i=0;i<N-1;i++){ans*=2;}

if(N==1){
if(A[0]%2==0 && P == 0) {printf("1"); return 0;}
if(A[0]%2==1 && P == 1) {printf("1"); return 0;}
printf("0"); return 0;
}

printf("%ld",ans);
return 0;
}

Measured memory_bytes: 128
let rec fix f x = f (fix f) x
let ( *@) a b = a * b mod 1000000007
let _ =
  Scanf.scanf "%d" @@ fun n ->
  let a = Array.init n (fun _ -> Scanf.scanf " %d" ((+) 0)) in
  let hats = [|0; 0; 0|] in
  (1, 0) |> fix (fun f (d, i) ->
    if i >= n then d else begin
      let c = Array.fold_left (fun c h -> if a.(i) = h then c+1 else c) 0 hats in
      0 |> fix (fun f j ->
        if j >= 3 then ()
        else if hats.(j) = a.(i) then hats.(j) <- hats.(j) + 1
        else f (j+1));
      f (c *@ d, i+1)
    end)
  |> Printf.printf "%d\n"




Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int D, N;
    cin >> D >> N;
    int T[D], A[N], B[N], C[N];
    for (int i = 0; i < D; i++) {
        cin >> T[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i] >> C[i];
    }
    int x[D][2];
    for (int i = 0; i < D; i++) {
        x[i][0] = 101;
        x[i][1] = -1;
    }
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (A[j] <= T[i] && T[i] <= B[j]) {
                x[i][0] = min(x[i][0], C[j]);
                x[i][1] = max(x[i][1], C[j]);
            }
        }
    }
    int dp[D][2]{};
    for (int i = 0; i < D - 1; i++) {
        dp[i + 1][0] = max(abs(x[i + 1][0] - x[i][0]) + dp[i][0], abs(x[i + 1][0] - x[i][1]) + dp[i][1]);
        dp[i + 1][1] = max(abs(x[i + 1][1] - x[i][0]) + dp[i][0], abs(x[i + 1][1] - x[i][1]) + dp[i][1]);
    }
    cout << max(dp[D - 1][0], dp[D - 1][1]) << "\n";
    return 0;
}


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

int main(){
    ll k;
    cin >> k;
    vector<ll> ans(50);
    for(int i = 0; i < 50; i++){
        ans[i] = i;
    }
    ll n = k/50; ll m = k%50;
    for(int i = 0; i < 50; i++){
        ans[i] += n;
    }
    for(int i = 49; i > 49-m; i--){
        ans[i]++;
    }
    cout << 50 << endl;
    for(int i = 0; i < 50; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 256