akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

int main() {
	int N, K;
	cin >> N >> K;
	priority_queue<ll>kind[N];
	for (int i = 0; i < N; ++i) {
		ll t, d;
		cin >> t >> d;
		kind[t - 1].push(d);
	}
	priority_queue<ll>best, remain;
	for (int i = 0; i < N; ++i) {
		if (!kind[i].empty()) {
			best.push(kind[i].top());
			kind[i].pop();
			while (!kind[i].empty()) {
				remain.push(kind[i].top());
				kind[i].pop();
			}
		}
	}
	vector<ll>bsum = { 0 };
	vector<ll>rsum = { 0 };
	while (!best.empty()) {
		bsum.push_back(bsum.back() + best.top());
		best.pop();
	}
	while (!remain.empty()) {
		rsum.push_back(rsum.back() + remain.top());
		remain.pop();
	}
	ll ans = 0;
	for (ll i = 1; i <= K; ++i) {
		if (i >= bsum.size())break;
		if (K - i >= rsum.size())continue;
		ans = max(ans, bsum[i] + rsum[K - i] + i * i);
	}
	cout << ans << endl;
	return 0;
}



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

int main() {
  int N;
  double x, ans=0;
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> x;
    ans = ans + 1/x;
  }
  
  cout << fixed;
  cout << setprecision(6) << 1 / ans << endl;;
}

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

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

using Graph = vector<vector<int>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}

typedef pair<int,int> P;

bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}
int factorial(int a){
  int res = 1;
  while(a){
    res *= a;
    a--;
  }
  return res;
}

int main(){
  int N;
  cin >> N;
  int x = 800 * N;
  int y = N/15 * 200;
  cout << x - y << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.TreeMap;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] d = new int[N];
    for (int i = 0; i < N; i++) {
      d[i] = sc.nextInt();
    }
    Arrays.sort(d);
    int half = N / 2;
    System.out.println(d[half] - d[half - 1]);
  }
}


Measured memory_bytes: 50240
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



int main() {
	int N;
	cin >> N;
	if (N < 1000) {
		cout << "ABC" << endl;
	}
	else {
		cout << "ABD" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define P(s) cout<<s<<"\n"

int32_t Group(int32_t n) {
    constexpr int32_t g[] = {0,1,3,1,2,1,2,1,1,2,1,2,1};
    return g[n];
}

int main() {
    int32_t x, y;
    cin >> x >> y;
    P((Group(x) == Group(y) ? "Yes": "No"));
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	while(!(a==b && b==0))
	{
		if(a>b)	cout<<b<<" "<<a<<endl;
		else 	cout<<a<<" "<<b<<endl;
		cin>>a>>b;
	}
	return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
#define int           long long
#define	pb            push_back
#define all(a)        (a).begin(),(a).end()
#define sz(x)         (int)x.size()
#define F             first
#define S             second
#define endl          "\n"
#define inf           1000000007
#define FOR(i, a, b)  for(int i=a; i<b; i++)
#define bigboi        1e18
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers. 
//int dp[333][2];	

void solve(){
	string s;
	cin>>s;
	int n = sz(s);
	int dp[n+1][2]={{0}};
	dp[0][1] = 1;
	FOR(i, 1, n+1){
		int k = s[i-1]-'0';
		dp[i][0] = min(dp[i-1][0]+k, dp[i-1][1]+10-k);
		dp[i][1] = min(dp[i-1][0]+k+1, dp[i-1][1]+10-k-1);
	}
	cout<<dp[n][0]<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 	
	int t=1;
	//cin>>t;
	FOR(i, 1, t+1){	
	//	cout<<"Case #"<<i<<":"<<endl;
		solve();
	}
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
 
}

Measured memory_bytes: 17052
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
using namespace std;
typedef long long unsigned int ll;
  
int main(){
string a;
 cin >> a;
 //cout << a.length() << endl;
 //cout << a[a.length()-1] << endl;
 if(a[a.length()-1] == 's'){
     a.append("es");
 }else{
     a.append("s");
 }
 cout << a << endl;
}


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

const int MAXN = 210;

struct node {
	int to, next;
	long long flow;
	int neg;
} edge[MAXN*MAXN];
int head[MAXN], top = 0;
inline void push(int i, int j, long long f)
{
	++top, edge[top] = (node) {j, head[i], f, top+1}, head[i] = top;
	++top, edge[top] = (node) {i, head[j], 0, top-1}, head[j] = top;
}

int vis[MAXN], lev[MAXN], bfstime = 0;
const int S = MAXN-1, T = MAXN-2;
queue<int> que;

bool bfs()
{
	vis[S] = ++bfstime, lev[S] = 0, que.push(S);
	while (!que.empty()) {
		int nd = que.front(); que.pop();
		for (int i = head[nd]; i; i = edge[i].next) {
			int to = edge[i].to;
			if (!edge[i].flow || vis[to] == bfstime) continue;
			vis[to] = bfstime, lev[to] = lev[nd]+1, que.push(to);
		}
	}
	return vis[T] == bfstime;
}

long long dfs(int nd, long long maxf)
{
	// cerr << nd << " " << maxf << endl;
	// cin.get();
	if (!maxf || nd == T) return maxf;
	long long ans = 0, t;
	for (int i = head[nd]; i; i = edge[i].next) {
		int to = edge[i].to;
		if (!edge[i].flow || lev[to] != lev[nd]+1) continue;
		t = dfs(to, min(maxf, edge[i].flow));
		ans += t, maxf -= t, edge[i].flow -= t, edge[edge[i].neg].flow += t;
	}
	// if (!maxf) lev[nd] = -1;
	return ans;
}

long long dinic()
{
	long long ans = 0;
	while (bfs()) {
		ans += dfs(S, 1e15);
		// cerr << vis[T] << " " << ans << endl;
	}
	return ans;
}

int n;
int a[MAXN];

int main()
{
	cin >> n;
	long long ans = 0;
	for (int i = 1; i <= n; i++) { cin >> a[i]; ans += a[i]; }
	for (int i = 1; i <= n; i++) push(S, i, 1e9), push(i, T, 1e9+a[i]);
	for (int i = 1; i <= n; i++)
		for (int j = i+i; j <= n; j += i)
			push(i, j, 1e15);
	// cerr << "HA" << endl;
	long long val = dinic()-(long long)n*1000000000;
	// cerr << val << endl;
	cout << ans-val << endl;
	return 0;
}


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

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;

int main () {
    int n;
    while (cin >> n, n) {
        vector<string> name(n);
        vector<lli> price(n, 0);
        vector<lli> tme(n, 0);
        REP (i, 0, n) {
            double P, A, B, C, D, E, F, S, M;
            cin >> name[i] >> P >> A >> B >> C >> D >> E >> F >> S >> M;
            price[i] = F * M * S - P;
            tme[i] = A + B + C + (D + E) * M;
        }
        vector<int> index(n);
        REP (i, 0, n) index[i] = i;
        sort(index.begin(), index.end(), [&name, &price, &tme](int a, int b) -> bool {
            if (price[a] * tme[b] == price[b] * tme[a]) return name[a] < name[b];
            else return price[a] * tme[b] > price[b] * tme[a];
        });
        REP (i, 0, n) {
            cout << name[index[i]] << endl;
        }
        cout << "#" << endl;
    }
    return 0;
}

Measured memory_bytes: 3228
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;


int main(){
    ll H, A;

    //input
    cin >> H >> A;

    if(H % A == 0){
        cout << H / A << endl;
    }else{
        cout << H / A + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.io.*;

class Main{
 public static void main(String[] args)throws IOException{
  int a,b,d,r;
  String f;
   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  
   String str = br.readLine(); 
   String[] strAry = str.split(" ");
   a = Integer.parseInt(strAry[0]);  
   b = Integer.parseInt(strAry[1]);   
   d = a/b;
   r = a%b;
   f=String.format("%.5f", ((double)a / (double)b));    
   
   f = String.format("%.5f", ((double)a / (double)b));
   System.out.println(d + " "+ r +" "+ f); 
 }
}

Measured memory_bytes: 24848
n = int(input())
s = input()
ans = 0

for i in range(1,n):
    s1 = s[:i]
    s2 = s[i:]
    S1 = list(set(s1))
    cnt = 0
    for j in range(len(S1)):
        if S1[j] in s2:
            cnt += 1
            ans = max(ans, cnt)
            
print(ans)

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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true; } return false; }

// const int INF = 1001001001;
// long long max => LLONG_MAX

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    int n4 = 0;
    int n2 = 0;
    int n1 = 0;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        if(a%4 == 0) n4++;
        else if (a%2 == 0) n2++;
        else n1++;
    }

    bool ans = false;
    if(n4 >= n/2) ans = true;
    if(n2 == n) ans = true;
    if(n4 >= n1) ans = true;

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

    return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    ll X, Y;
    cin >> X >> Y;
    if (X % Y == 0)
        cout << -1 << endl;
    else
        cout << X << endl;
    return 0;
}

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

int main(){
  int sic,sh,sm,eic,eh,em,st,et,S,E,flag,ans;
  int d[8][8];
  bool c[8][8];
  d[1][2]=d[2][1]=300;
  d[1][3]=d[3][1]=500;
  d[1][4]=d[4][1]=600;
  d[1][5]=d[5][1]=700;
  d[1][6]=d[6][1]=1350;
  d[1][7]=d[7][1]=1650;
  d[2][3]=d[3][2]=350;
  d[2][4]=d[4][2]=450;
  d[2][5]=d[5][2]=600;
  d[2][6]=d[6][2]=1150;
  d[2][7]=d[7][2]=1500;
  d[3][4]=d[4][3]=250;
  d[3][5]=d[5][3]=400;
  d[3][6]=d[6][3]=1000;
  d[3][7]=d[7][3]=1350;
  d[4][5]=d[5][4]=250;
  d[4][6]=d[6][4]=850;
  d[4][7]=d[7][4]=1300;
  d[5][6]=d[6][5]=600;
  d[5][7]=d[7][5]=1150;
  d[6][7]=d[7][6]=500;
  S=17*3600+30*60;
  E=19*3600+30*60;
  for(int i=1;i<8;i++)
    for(int j=1;j<8;j++) c[i][j]=true;
  c[1][6]=c[6][1]=false;
  c[3][7]=c[7][3]=false;
  c[2][7]=c[7][2]=false;
  c[1][7]=c[7][1]=false;
  while(1){
    cin>>sic>>sh>>sm>>eic>>eh>>em;
    if(!sic) break;
    st=sh*3600+sm*60;
    et=eh*3600+em*60;
    flag=0;
    if((S<=st&&st<=E)||(S<=et&&et<=E)) flag=1;
    ans=d[sic][eic];
    if(flag&&c[sic][eic]){
      int cal;
      ans/=2;
      cal=ans%100;
      if(cal%50){
	ans/=100;
	ans*=100;
	if(cal<50) ans+=50;
	else ans+=100;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

using namespace std;

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

using ll = long long;
using pint = pair<int, int>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

int main(){

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

    int n, m;
    cin >> n >> m;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
    map<ll, ll> mp;
    rep(i, n){
        int tmp;
        cin >> tmp;
        mp[tmp]++;
    }

    rep(i, m){
        ll b, c;
        cin >> b >> c;
        mp[c] += b;
    }

    ll cnt = 0ll;
    ll ans = 0ll;

    for(auto itr = mp.rbegin(); itr != mp.rend(); ++itr){
        pair<ll,ll> p = *itr;
        if(cnt > n) break;
        if(cnt+p.second <= n){
            ans += p.first*p.second;
            cnt += p.second;
        }
        else{
            ans += p.first*(n-cnt);
            break;
        }
    }
    ppp(ans);

    //
    //
    // while(!q.empty()){
    //     cerr << q.top() << endl;
    //     q.pop();
    // }





    return 0;
}


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

int main() {
	string S;
	vector <int> r(100000,0), l(100000,0), ans(100000,0);
	cin >> S;
	r[0] = 1;
	l[S.length()-1] = 1;
	
	for (int i = 0; i < S.length(); i++){
		if(i > 0 && S[i] == 'R'){
			r[i] = r[i-1] + 1;
			r[i-1] = 0;
		}
	}
	for (int i = S.length()-1; i >=0; i--){
		if(i < S.length()-1 && S[i] == 'L'){
			l[i] = l[i+1] + 1;
			l[i+1] = 0;
		}
	}
	for (int i = 0; i < S.length(); i++){
		if(r[i] > 0){
			ans[i] += (int) ((r[i] + 1)  / 2);
			ans[i+1] += (int) (r[i] / 2);
		}
	}
	for (int i = S.length()-1; i >=0; i--){
		if(l[i] > 0){
			ans[i] += (int) ((l[i] + 1)  / 2);
			ans[i-1] += (int) (l[i] / 2);
		}
	}
	for (int i = 0; i < S.length(); i++){
		//cout << r[i] << " ";
		cout << ans[i] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
vector<ll> temp;
vector<vector<ll>> v;
ll n, m, q, ans = 0;
void solve(int idx, int numb){
    if(idx >= n){
        v.push_back(temp);
        return;
    }
    for(int i = numb; i <= m; i++){
        temp[idx] = i;
        solve(idx + 1, i);
    }
}
int main(){
    Hello
    cin >> n >> m >> q;
    ll a[q], b[q], c[q], d[q];
    for(int i = 0; i < q; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    temp.resize(n);
    solve(0, 1);
    for(int i = 0; i < v.size(); i++){
        ll cur = 0;
        for(int k = 0; k < q; k++)
            if(v[i][b[k] - 1] - v[i][a[k] - 1] == c[k])
                cur += d[k];
        ans = max(ans, cur);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 13876
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using System.Threading;
using System.Threading.Tasks;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var S = cin.Read;
            var s = new Stack<char>();
            var ans = 0;
            foreach (var c in S.ToCharArray())
            {
                if (s.Count > 0 && c != s.Peek())
                {
                    s.Pop();
                    ans += 2;
                }
                else
                {
                    s.Push(c);
                }
            }

            Console.WriteLine(ans);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}


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

#define _u(i,a,b) for(int i=a;i<=b;++i)
#define _d(i,a,b) for(int i=a;i>=b;--i)
#define endl "\n"
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define FIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FI(task) freopen(task".inp","r",stdin)
#define FO(task) freopen(task".out","w",stdout)

using namespace std;

const int N = 3e3+7;
const int M = 1e9+7;

double f[N][N], p[N];
int n;

#define task "test"

int main(){
    FIO();
    //FI(task);
    ///FO(task);

    cin >> n;
    _u(i,1,n) cin >> p[i];
    _u(i,1,1){
        f[i][1] = p[i];
        f[i][0] = 1-p[i];
    }
    _u(i,2,n)
    _u(j,0,i){
        f[i][j] += f[i-1][j]*(1-p[i]);
        if(j==0) continue;
        f[i][j] += f[i-1][j-1]*p[i];
    }
    double res(0);
    _u(i,(n+1)/2,n) res += f[n][i];
    cout << setprecision(10) << fixed << res;
    return 0;
}


Measured memory_bytes: 69120
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;

ll n,l,sum,a=1e9;

int main()
{

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

    cin >> n >> l;
    for(ll i=1; i<=n; i++){
        sum+=l+i-1;
        if( abs(l+i-1) < abs(a) ) a = l+i-1;
    }

    cout << sum-a;

    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (N, M, X, Y) = readLine()!!.split(' ').map(String::toInt)
    val x = readLine()!!.split(' ').map(String::toInt).sorted()
    val y = readLine()!!.split(' ').map(String::toInt).sorted()
    if (x[N-1] >= y[0] || x[N-1] >= Y || y[0] <= X) {
        println("War")
    }
    else {
        println("No War")
    }
}

Measured memory_bytes: 38244
#include <stdio.h>
#include <math.h>
#define N 10000

main(){
  int n, count = 0, i, a[N], j, b;

  scanf("%d", &n);
  for(i = 0;i < n;i++){
    scanf("%d", &a[i]);
  }
  for(i = 0;i < n;i++){
    b = 1;
    if(a[i] == 2){
      b = 1;
    }
    else if(a[i] % 2 == 0){
      continue;
    }
    else if(a[i] % 2 != 0){ 
      for(j = 3;j <= sqrt(a[i]);j+=2){
	if(a[i] % j == 0){
	  b = 0;
	  break;
	}
      }
    }
    if(b == 1){
      count++; 
    }
  }
  printf("%d\n", count);
  return 0;
} 

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

const int maxN=2004;

int n,sol;
int v[maxN];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    sort(v+1,v+n+1);

    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            int sum=v[i]+v[j];
            
            int lef=j+1;
            int rig=lower_bound(v+1,v+n+1,sum)-v;
            
            sol+=rig-lef;
        }
    }

    cout<<sol;

    return 0;
}

Measured memory_bytes: 256
while True:
    n = int(input())
    if n == 0:
        break
    C = input().split()
    D = {}
    for x in [chr(i) for i in range(65, 65+26)]:
        D[x] = 0 
    for i in range(n):
        D[C[i]] += 1
        E = sorted(D.items(), key=lambda x: x[1], reverse=True)
        if E[0][1] > E[1][1] + n - i - 1:
            print(E[0][0], i + 1)
            break
    if E[0][1] == E[1][1]:
        print("TIE")


Measured memory_bytes: 5624
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-6;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,1,1,1,0},DY[8]={1,0,-1,-1,-1,0,1,1};

template <class T>

class Lazy_Segment_Tree{
	private:
	int n;
	vector<T> date,lazy;
	void Set_Lazy(int k,T x){
		date[k]+=x;
		lazy[k]+=x;
	}
	void Push(int k){
		Set_Lazy(k*2+1,lazy[k]);
		Set_Lazy(k*2+2,lazy[k]);
		lazy[k]=0;
	}
	void Fix(int k){
		date[k]=min(date[k*2+1],date[k*2+2]);
	}
	void Add_func(int a,int b,int k,int l,int r,T x){
		if(r<=a||b<=l) return;
		if(a<=l&&r<=b){
			Set_Lazy(k,x);
			return;
		}
		Push(k);
		int m=(l+r)/2;
		Add_func(a,b,k*2+1,l,m,x);
		Add_func(a,b,k*2+2,m,r,x);
		Fix(k);
	}
	void Update_func(int I,int k,int l,int r,T x){
		if(r<=I||I<l) return;
		if(l==I&&r-l==1){
			date[k]=x;
			lazy[k]=x;
			return;
		}
		Push(k);
		int m=(l+r)/2;
		Update_func(I,k*2+1,l,m,x);
		Update_func(I,k*2+2,m,r,x);
		Fix(k);
	}
	T Query_func(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return INF;
		if(a<=l&&r<=b) return date[k];
		Push(k);
		int m=(l+r)/2;
		T vl=Query_func(a,b,k*2+1,l,m);
		T vr=Query_func(a,b,k*2+2,m,r);
		return min(vl,vr);
	}
	public:
	Lazy_Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=lazy=vector<T>(2*n-1,INF);
	}
	void Add(int a,int b,T x){
		Add_func(a,b,0,0,n,x);
	}
	void Update(int k,T x){
		Update_func(k,0,0,n,x);
	}
	T Query(int a,int b){
		return Query_func(a,b,0,0,n);
	}
	T Open(int k){
		k+=n-1;
		T res=date[k];
		while(k>0){
			k=(k-1)/2;
			res+=lazy[k];
		}
		return res;
	}
	void Full_Open(){
		for(int i=0;i<2*n-1;i++) cout<<date[i]<<' ';
		cout<<endl;
		for(int i=0;i<2*n-1;i++) cout<<lazy[i]<<' ';
		cout<<endl;
	}
};

ll n,a,b,q;

int main(){
	cin>>n>>q>>a>>b;
	a--;b--;
	Lazy_Segment_Tree<ll> ls1(n),ls2(n);
	for(ll i=0;i<n;i++){
		ls1.Update(i,abs(a-i)+i);
		ls2.Update(i,abs(a-i)-i);
	}/*
	ls1.Update(a,a);
	ls2.Update(a,-a);*/
	ll l=b;
	for(int i=0;i<q;i++){
		ll x;
		cin>>x;
		x--;
		ll lm=ls1.Query(x,n),rm=ls2.Query(0,x),DP=min(lm-x,rm+x);
		ls1.Update(l,DP+l);
		ls2.Update(l,DP-l);
		ll add=abs(x-l);
		ls1.Add(0,l,add);
		ls2.Add(0,l,add);
		ls1.Add(l+1,n,add);
		ls2.Add(l+1,n,add);
		l=x;
	}
	ll res=INF;
	for(ll i=0;i<n;i++) res=min(res,ls1.Open(i)-i);
	cout<<res<<endl;
}

Measured memory_bytes: 16768
while (line = gets.to_i) != 0 do
  array = []
  line.times do |i|
    array << gets.to_i
  end
  array.sort!
  sum = 0
  (1..array.size - 2).each do |i|
    sum += array[i]
  end
  puts sum / (array.size - 2)
end


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

using ll = long long;
using namespace std;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
ll MOD=1e9+7;


int main(){
  int D;
  cin>>D;
  vector<int> c(26+1);
  for(int i(1);i<27;i++){
    cin>>c[i];
  }
  vector<vector<int>> s(D+1,vector<int>(26+1));
  for(int i(1);i<=D;i++){
    for(int j(1);j<=26;j++){
      cin>>s[i][j];
    }
  }
  vector<int> t(D+1);
  int nowp(0);
  vector<int> l(D,0);
  for(int i(1);i<=D;i++){
    int maxj(0),maxp(-1e9);
    for(int j(1);j<=26;j++){
      //i日目がj番目の場合
      int tmp(nowp);
      tmp += s[i][j];
      for(int k(1);k<=26;k++){ //ここ一度和を計算しておけば、何回も引くものを計算しなくても良い
        if(k == j) continue;
        tmp -= c[k]*(i - l[k]);
      }
      if(maxp < tmp) {
        maxj = j;
        maxp = tmp;
      }
    }
    t[i] = maxj;
    // 貪欲的にmaxj番目と決める
    nowp += s[i][maxj];
    l[maxj] = i;
    for(int j(1);j<=26;j++){
      nowp -= c[j]*(i - l[j]);
    }
  }

  for(int i(1);i<=D;i++){
    cout << t[i] << endl;
  }
  return 0;
}



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

using namespace std;

int calc(string s, char c) {

    int cnt = 0, n = s.size();
    for(int i = 0; i < n; i++)
        if((i % 2 && s[i] == c) || (i % 2 == 0 && s[i] != c))
            cnt++;
    
    return cnt;
}

int main() {

    string s;
    cin >> s;
    
    cout << min(calc(s, '0'), calc(s, '1')) << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"
#define MOD 100000009

using namespace std;

typedef long long int lli;

const int NMAX = 100005;
int parent[NMAX];
bool used[NMAX];

int get_parent(int a){
	if(parent[a] == a) return a;
	return parent[a] = get_parent(parent[a]);
}

void unite(int a, int b){
	int para = get_parent(a);
	int parb = get_parent(b);
	parent[para] = parb;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for(int i=0; i<n; i++) parent[i] = i;
	for(int i=0; i<m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		x--;
		y--;
		unite(x, y);
	}

	int res=0;
	for(int i=0; i<n; i++){
		if(!used[get_parent(i)]){
			res++;
			used[get_parent(i)] = 1;
		}
	}
	cout << res;

	return 0;
}

Measured memory_bytes: 1152
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel.Design;
using System.Globalization;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Threading.Tasks;
using System.Xml.Schema;
using static System.Console;

namespace ConsoleApp2
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<int> Slist() {
            var t = ReadLine();
            if (t.Trim().Length == 0) return new List<int>();
            return new List<int>(t.Split().Select(int.Parse)); }
        static void Main(string[] args)
        {
            var AB = Sarray();
            var A = AB[0];
            var B = AB[1];
            var g = (gcd(A, B));
            WriteLine(A * B / g);

        }

        static long gcd(long a, long b)
        {
            if (b == 0) return a;
            if(a<b)
            {
                var t = a;
                a = b;
                b = t;
            }
            return gcd(b, a % b);
        }
    }
}


Measured memory_bytes: 18900
import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = list(map(int, input().strip().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

print(ans)

Measured memory_bytes: 101848
#!/usr/bin/env python3

n = int(input())
a = [int(x) for x in input().split()]

m = 1
l = 0
while m < n:
    m *= 2
    l += 1
tr = [0] * (2 * m)

tr[m:m + n] = a


def gcd(a, b):
    if not a:
        return b
    while b:
        r = a % b
        a, b = b, r
    return a


def init_tr():
    for d in range(l - 1, -1, -1):
        for i in range(1 << d, 1 << (d + 1)):
            tr[i] = gcd(tr[i * 2], tr[i * 2 + 1])


def upd_tr(j):
    i = j // 2
    if i == 0:
        return
    tr[i] = gcd(tr[i * 2], tr[i * 2 + 1])
    upd_tr(i)


init_tr()

ans = 0

for i in range(n):
    tmp = tr[m + i]
    tr[m + i] = 0
    upd_tr(m + i)
    ans = max(ans, tr[1])
    tr[m + i] = tmp
    upd_tr(m + i)

print(ans)


Measured memory_bytes: 75628
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())

dp = [0] * (N + 1)

for i in range(1, N + 1):
    x = i
    for j in range(2, i):
        while x % j == 0:
            x //= j
            dp[j] += 1
    if x != 1:
        dp[x] += 1
# dp = sorted(dp, reverse=True)

ans = 0
ans += any(x for x in dp if x >= 74)

x = 0
y = 0
for i in range(N + 1):
    if dp[i] >= 24:
        x += 1
    if dp[i] >= 2:
        y += 1
ans += x * (y - 1)

x = 0
y = 0
for i in range(N + 1):
    if dp[i] >= 14:
        x += 1
    if dp[i] >= 4:
        y += 1
ans += x * (y - 1)

x = 0
y = 0
z = 0
for i in range(N + 1):
    if dp[i] >= 4:
        x += 1
        y += 1
    if dp[i] >= 2:
        z += 1
ans += x * (y - 1) * (z - 2) // 2
# print(dp)
# print(x, y, z)

print(ans)

Measured memory_bytes: 3440
import java.util.Scanner;
class Main{
	static Scanner s = new Scanner(System.in);
	public static void main(String[] args) {
		int	x = Integer.parseInt(s.next()),
			y = Integer.parseInt(s.next());
		System.out.print  (x*y);
		System.out.print  (" ");
		System.out.println((x+y)*2);
	}
}

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

using namespace std;

#define ll long long
#define pii pair<int, int>

#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char dir[] = {'R', 'L', 'D', 'U'};
const int MOD = 1e9 + 7;

void solve()
{
    int n; cin >> n;
    int rolls[n][n];
    for(int i = 0; i < n; i++) cin >> rolls[i][0] >> rolls[i][1];
    for(int i = 0; i < n - 2; i++)
    {
        if(rolls[i][0] == rolls[i][1] && rolls[i + 1][0] == rolls[i + 1][1] && rolls[i + 2][0] == rolls[i + 2][1])
        {
            cout << "Yes";
            return;
        }
    }
    cout << "No";
}

int main()
{
    fastio

    //ifstream fin(".in");
    //ofstream fout(".out");


    int t = 1;
    //cin >> t;

    while(t-- > 0) solve();
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define ulli unsigned lli
#define ld long double
#define pb push_back
#define mp make_pair
#define bp pop_back
#define vi vector<int>
#define vvi vector< vector<int> >
#define vli vector<lli>
#define vvli vector< vector<lli> >
#define pii pair <int, int>
#define pli pair <lli, lli>
#define forn(i,n) for(i=0;i<n;i++)
#define FORN(i,k,n) for(i=k;i<n;i++)
#define rof(i,k,n) for(i=k;i>=n;i--)
#define wh(k) while(k--)
#define mod 1000000007
#define set(a,s) memset(a,s,sizeof(a))

int main()
{
	fast;
	int n,i;
	cin>>n;
	int a[n],b[n],c[n-1];
	forn(i,n)
	cin>>a[i];
	forn(i,n)
	cin>>b[i];
	forn(i,n-1)
	cin>>c[i];
	int count=0;
	count+=b[a[0]-1];
	int temp=a[0];
	for(i=1;i<n;i++)
	{
		count+=b[a[i]-1];
		if(a[i]==temp+1)
		count+=(c[temp-1]);
		temp=a[i];
	}
	cout<<count<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef uint B;

#define mask 0x07

#define get(d,i) (((d) >> ((i)*3)) & mask)

#define set(d,i,n) {d &= ~(mask << ((i)*3)); d |= (n << (3*(i)));}

#define get2(d,x,y) get(d, x+y*4)

#define set2(d,x,y,n) set(d, x+y*4, n)

#define ABS(x) ((x)<0?-(x):(x))

static inline B swap(B b, int p1, int p2){
  int d1 = get(b, p1);
  int d2 = get(b, p2);
  set(b, p1, d2);
  set(b, p2, d1);
  return b;
}

#define swap2(b,x1,y1,x2,y2) swap(b, (x1)+(y1)*4, (x2)+(y2)*4)


B q[8*7*6*5*4*3*2*1 + 10];
int flag[1<<24];

int main(){
  int tmp;
  B ans = 0; REP(i,8) set(ans,i,i);

  int head = 0;
  int tail = 0;
  q[tail++] = ans;
  flag[ans] = 1;

  while(head != tail){
    B bb = q[head++];
    int nn = flag[bb];

    REP(y,2) REP(x,4){
      if(get2(bb,x,y) == 0){
        if(y == 0){
          B bbb = swap2(bb,x,y,x,y+1);
          if(!flag[bbb]){
            flag[bbb] = nn + 1;
            q[tail++] = bbb;
          }
        }else{
          B bbb = swap2(bb,x,y,x,y-1);
          if(!flag[bbb]){
            flag[bbb] = nn + 1;
            q[tail++] = bbb;
          }
        }
        if(x != 0){
          B bbb = swap2(bb,x,y,x-1,y);
          if(!flag[bbb]){
            flag[bbb] = nn + 1;
            q[tail++] = bbb;
          }
        }
        if(x != 3){
          B bbb = swap2(bb,x,y,x+1,y);
          if(!flag[bbb]){
            flag[bbb] = nn + 1;
            q[tail++] = bbb;
          }
        }
      }
    }
  }
  while(~scanf("%d",&tmp)){
    B b = 0;
    set(b,0,tmp);
    REP(i,7){
      scanf("%d",&tmp);
      set(b,i+1,tmp);
    }
    printf("%d\n",flag[b]-1);
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main {

	static int n;
	static double[] x1, y1, x2, y2;
	static double sx, sy, gx, gy;
	static Point[][] seg;
	static ArrayList<Integer>[] g;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int q = sc.nextInt();
		while (q-- > 0) {
			Point s1 = new Point(sc.nextDouble(), sc.nextDouble());
			Point d1 = new Point(sc.nextDouble(), sc.nextDouble());
			Point s2 = new Point(sc.nextDouble(), sc.nextDouble());
			Point d2 = new Point(sc.nextDouble(), sc.nextDouble());
			if (linesIntersect(s1, d1, s2, d2)) {
				System.out.println(1);
			} else {
				System.out.println(0);
			}
		}
		// ArrayList<Point> ps = new ArrayList<>();
		// n = sc.nextInt();
		// x1 = new double[n];
		// y1 = new double[n];
		// x2 = new double[n];
		// y2 = new double[n];
		// seg = new Point[n][2];
		// for (int i = 0; i < n; ++i) {
		// x1[i] = sc.nextDouble();
		// y1[i] = sc.nextDouble();
		// x2[i] = sc.nextDouble();
		// y2[i] = sc.nextDouble();
		// Point p1 = new Point(x1[i], y1[i]);
		// Point p2 = new Point(x2[i], y2[i]);
		// ps.add(p1);
		// ps.add(p2);
		// seg[i] = new Point[] { p1, p2 };
		// }
		// sx = sc.nextDouble();
		// sy = sc.nextDouble();
		// gx = sc.nextDouble();
		// gy = sc.nextDouble();
		// for (int i = 0; i < n; ++i) {
		//
		// }
	}

	static int gen = 0;

	static class Point {
		double x, y;
		int id;

		public Point(double x1, double y1) {
			this.x = x1;
			this.y = y1;
			id = gen++;
		}
	}

	static boolean linesIntersect(Point s1, Point d1, Point s2, Point d2) {
		long prd1 = ccw(s1, d1, d2) * ccw(s1, d1, s2);
		long prd2 = ccw(s2, d2, s1) * ccw(s2, d2, d1);
		return prd1 <= 0 && prd2 <= 0;
	}

	static long ccw(Point s, Point d, Point p) {
		double cp = crossProduct(s, d, s, p);
		if (cp != 0)
			return Double.compare(cp, 0);
		else {
			if (dotProduct(s, d, s, p) < 0)
				return -2;
			else if (dotProduct(d, s, d, p) < 0)
				return 2;
			else
				return 0;
		}
	}

	static double crossProduct(Point s1, Point d1, Point s2, Point d2) {
		return (d1.x - s1.x) * (d2.y - s2.y) - (d1.y - s1.y) * (d2.x - s2.x);
	}

	static double dotProduct(Point s1, Point d1, Point s2, Point d2) {
		return (d1.x - s1.x) * (d2.x - s2.x) + (d1.y - s1.y) * (d2.y - s2.y);
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 57356
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = map(int, raw_input().split())
DP = [0] * (N + 2)

for i in range(M):
    L, R = map(int, raw_input().split())
    DP[L] += 1
    DP[R + 1] -= 1

for i in range(N + 1):
    DP[i + 1] += DP[i]

print sum(num == M for num in DP)

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

int main() {
    int L, R, d;
    cin >> L >> R >> d;

    int cnt = 0;
    for (int i = L; i <= R; i++) {
        if (i % d == 0) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3624
#include <iostream>
    #include <string>
    #include <set>  
    #include <stack>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    #include <queue>
    #include <deque>
    #include <cstring>
    #include <cstdio>
    #include <map>
    #include <numeric>
    #include <cassert>
    #include <iomanip>
    #include <sstream>
    #include <ctime>
    #include <bitset> 
    #include <unordered_map>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,maxn) for1(i,0,maxn)
#define ford(i,b,a) for(int i=(int)(b)-1;i>=a;--i)
typedef long long ll;
typedef unsigned long long int128;
typedef pair<int,int> pii;
typedef pair<int,pii > piii;
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define mod1 1000000007
#define mod2 998244353
#define eps 1e-10
#define pi acos(-1)
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define dprintf(...) printf(__VA_ARGS__)
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1^1)
const int maxn=1e5+7;
int n,k,zpos;
ll pos[maxn];
ll sumlft[maxn],sumrht[maxn];
int main()
{
	scanf("%d%d",&n,&k);
	zpos=-1;
	rep(i,n)
	{
		scanf("%lld",pos+i);
		if(i&&pos[i-1]<0&&pos[i]>=0)
			zpos=i;
	}
	if(zpos==-1)
		zpos=(pos[0]>=0?0:n);
	memset(sumrht,0x3f,sizeof(sumrht));
	for(int i=zpos;i<n;i++)
		sumrht[i-zpos]=pos[i];//cout<<i-zpos<<" "<<sumrht[i-zpos]<<endl;
	memset(sumlft,0x3f,sizeof(sumlft));
	for(int i=zpos-1;i>=0;i--)
		sumlft[zpos-1-i]=-pos[i];//cout<<zpos-1-i<<" "<<sumlft[zpos-i-1]<<endl;
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(int lft=0;lft<=min(k,zpos);lft++)
	{
		int rht=k-lft;
		if(rht>(n-zpos))continue;
		ll lftsum=(lft?sumlft[lft-1]:0);
		ll rhtsum=(rht?sumrht[rht-1]:0);
		ll res=lftsum+rhtsum+1ll*min(lftsum,rhtsum);
	//	cout<<lft<<" "<<rht<<" "<<lftsum<<" "<<rhtsum<<" "<<min(lftsum,rhtsum)<<endl;
	//	cout<<ans<<" "<<res<<endl;
		ans=min(ans,res);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <algorithm>

using namespace std;
#define n_max 100000
#define M_max 50
#define N_max 50


int main()
{
    int N, M; 
    int num[N_max];
    int p[M_max][2];
    int path[N_max];

    cin >> N >> M;
    
    for(int i = 0; i < N; i++) {
        path[i] = 0;
        num[i] = 0;
    }

    for(int i = 0; i < M; i++) {
        cin >> p[i][0] >> p[i][1]; 
    }

    for(int i = 0; i < M; i++) {
        num[p[i][0] - 1]++;
        num[p[i][1] - 1]++;
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
int main(){
  ios::sync_with_stdio(false);
  ll n;
  cin>>n;
  vector<ll> a(n),b(n),c(n);
  rep(i,n) cin>>a[i];
  rep(i,n) cin>>b[i];
  rep(i,n) cin>>c[i];
  sort(ALL(a));
  sort(ALL(b));
  sort(ALL(c));
  ll cnt=0;
  for(ll i=0;i<n;i++){
    ll x = (ll)(lower_bound(ALL(a),b[i])-a.begin());
    ll y = (ll)(c.end()-upper_bound(ALL(c),b[i]));
    cnt+=x*y;
  }
  cout<<cnt<<"\n";


}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}


int main(){
  ll k,n;
  cin >> k >> n;
  vector<ll> a(n);
  for(auto &&x:a)cin>>x;
  ll ans = MOD;
  FOR(i,0,n-1){
    ans = min(ans,ll(k-a[i+1]+a[i]));
  }
  ans = min(ans,a[n-1]-a[0]);
  cout << ans << endl;
}

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

int main(){
  string S;
  cin >> S;
  map<char,int> m;
  string alpha = "abcdefghijklmnopqrstuvwxyz";

  for(int i = 0; i < S.size();i++){
    m[S[i]]++;
  }

  for(int j = 0;j < 26; j++){
    if(m[alpha[j]] == 0){
    cout << alpha[j] << endl;
    return 0;
    }
    if(j == 25)
    cout << "None" << endl;
  
  }

  return 0;

  
  
}

Measured memory_bytes: 512
def calc_length(node, step)
  @edge[node].each do |next_node|
    if @length[next_node][(step+1)%3] > 0
      next
    else
      @length[next_node][(step+1)%3] = step+1
    end
    @queue.push([next_node, step+1])
  end
end

n, m = gets.chomp.split.map(&:to_i)
@edge = Array.new(n+1){[]} # インデックスの補正
m.times do |_|
  v1, v2 = gets.chomp.split.map(&:to_i)
  @edge[v1].push(v2)
end
s, t = gets.chomp.split.map(&:to_i)

@queue = [[s,0]]
@length = Array.new(n+1) { Array.new(3, 0) }

until @queue.empty?
  #p @length
  node, step = @queue.shift
  if node == t && (step%3 == 0)
    puts step / 3
    exit 0
  end
  
  calc_length(node, step)
end

puts "-1"


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

int main() {
    string s, t;
    while (cin >> s >> t) {
        if (s == "0" && t == "0") break;
        int hit = 0, blow = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (s[i] == t[j]) {
                    blow++;
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            if (s[i] == t[i]) {
                blow--;
                hit++;
            }
        }
        cout << hit << ' ' << blow << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int V = 1e5+5;
vector<int> to[V*2];
bool visited[V*2];
vector<int>cnt;

void dfs(int v){
  if(visited[v])return;
  visited[v] = true;
  cnt[v/V]++;
  for(int u:to[v]) dfs(u);
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N;cin >> N;
  rep(i,N){
    int x,y;cin >> x >> y;
    y += V;
    to[x].push_back(y);
    to[y].push_back(x);
  }

  ll ans = 0;
  rep(i,V){
    if(visited[i]) continue;
    cnt = vector<int>(2,0);
    dfs(i);
    ans += (ll)cnt[0]*cnt[1];
  }
  ans -= N;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 10240
n = int(input())

if (n >= 1) and (n <= 8):
    print(n)
elif (n >= 9) and (n <= 99):
    print(9)
elif (n >= 100) and (n <= 998):
    print(n - 90)
elif (n >= 999) and (n <= 9999):
    print(909)
elif (n >= 10000) and (n <= 99998):
    print(n - 9090)
else:
    print(90909)

Measured memory_bytes: 3060
n, k = map(int, input().split())
p = list(map(int, input().split()))

s = [0]
sum_ = 0
for i in range(1, 1001):
    sum_ += i
    s.append(sum_)

b = []
for i in range(n):
    b.append(s[p[i]] / p[i])

bcum = [0] * (n+1)
for i in range(n):
    bcum[i+1] = bcum[i] + b[i]

ans = 0
for i in range(n+1-k):
    ans = max(ans, bcum[i+k] - bcum[i])

print(ans)

Measured memory_bytes: 81800