akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
int main()
{
	ll n , t;
	cin >> n >> t;
	ll a[n];
	for(int i = 0 ; i < n ; i++)
		cin >> a[i];
	sort(a , a + n);
	ll ans = 0;
	ll x = 0;
	for(int i = 0 ; i < n ; i++){
		if(a[i] < x)
			ans = ans - (x - a[i]);
		x = a[i] + t;
		ans += t;
	}
	cout << ans << endl;
	return 0;
} 




Measured memory_bytes: 1792
import math
from decimal import *

def main():
    votes = int(input())
    ratio = [[ int(i) for i in input().split() ] for j in range(votes)]

    votesTemp = [0, 0]
    for i in range(votes):
        if i == 0:
            votesTemp = ratio[i]
            continue

        ceil = [ math.ceil(Decimal(votesTemp[j]) / Decimal(ratio[i][j])) for j in range(2)]

        votesTemp = [ max(ceil) * ratio[i][j] for j in range(2) ]

        """
        print("turn: " + str(i))
        print("votes: " + str(ratio[i][0]) + ":" + str(ratio[i][1]) )
        print("Temp: " +str(votesTemp[0])+":"+str(votesTemp[1]))
        """
    print(sum(votesTemp))

if __name__ == '__main__':
  main()


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

using namespace std;

void solve()
{
	string str;
	while(cin >> str)
	{
		int count1 = 0;
		int count2 = 0;
		for(int i = 0; i < str.size() - 2; ++i)
		{
			if(str[i] == 'J' && str[i + 1] == 'O' && str[i + 2] == 'I')
			{
				++count1;
			}
			else if(str[i] == 'I' && str[i + 1] == 'O' && str[i + 2] == 'I')
			{
				++count2;
			}
		}
		cout << count1 << endl;
		cout << count2 << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}

vvi con(100050);
V(bool) visited(100050, false);
vi bw(100050, 0);
bool exr = false;

void dfs(int now, int cost, int past) {
    bw[now] = cost%2;
    rep(i, con[now].size()) {
        if(!visited[con[now][i]]) {
            visited[con[now][i]] = true;
            dfs(con[now][i], cost+1, now);
        } else if(con[now][i] != past) {
            if(bw[con[now][i]]==bw[now]) exr = true;
        }
    }
}

signed main() {
    int N, M;
    cin >> N >> M;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        con[a].pb(b);
        con[b].pb(a);
    }

    dfs(0, 0, -1);
    
    if(exr) cout << N*(N-1)/2 - M << endl;
    else {
        int b=0, w=0;
        rep(i, N) {
            if(bw[i]==0) b++;
            else w++;
        }
        cout << b*w-M << endl;
    }
        
    
    return 0;
}

Measured memory_bytes: 8448
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[][] ary = new int[n][2];
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            ary[i][0] = Integer.parseInt(sc.next());
            ary[i][1] = Integer.parseInt(sc.next());
            sb.append(i);
        }
        permute(list, sb.toString(), 0, n - 1);
        double sum = 0;
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            for (int j = 0; j < n - 1; j++) {
                int a = Integer.parseInt(String.valueOf(s.charAt(j)));
                int b = Integer.parseInt(String.valueOf(s.charAt(j + 1)));
                sum += Math.sqrt(Math.pow(ary[a][0] - ary[b][0], 2) + Math.pow(ary[a][1] - ary[b][1], 2));
            }
        }
        System.out.println(sum / factorial(n));
    }

    private static void permute(List<String> list, String str, int l, int r) {
        if (l == r) {
            list.add(str);
        } else {
            for (int i = l; i <= r; i++) {
                str = swap(str, l, i);
                permute(list, str, l + 1, r);
                str = swap(str, l, i);
            }
        }
    }

    private static String swap(String a, int i, int j) {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    private static long factorial(long n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

Measured memory_bytes: 45504
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
   string s, t; cin >> s >> t;

   t.pop_back();
   
   if(s == t) cout << "Yes" << ln;
   else cout << "No" << ln;
}


Measured memory_bytes: 3640
T = list(input())
N = len(T)
count = 0
for i in range(N):
    if T[i] == '?':
        T[i] = 'D'
    if (i < N - 1) and T[i] == 'P' and T[i + 1] == 'D':
        count += 1
    elif T[i] == 'D':
        count += 1

#print(count)
ans = ''.join(T)
print(ans)

Measured memory_bytes: 10844
#include <cstdio>

bool is_prime(int x)
{
	int i;

	for (i = 2; i * i <= x; i++)
		if (x % i == 0)
			return false;
	return true;
}

int main(void)
{
	int n, i;

	scanf("%d" ,&n);

	int cnt = 0;
	for (i = 11; ; i += 10)
	{
		if (is_prime(i))
		{
			printf("%d " ,i);
			++cnt;
		}

		if (cnt >= n)
			break;
	}
	return 0;
}

Measured memory_bytes: 128
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	a = [Array{Int,1}(n-1) for i in 1:n]
	for i in 1:n
		a[i] = readline() |> split |> parseMap
	end
	f = 0
	k = 0
	l = (n-1)*n
	b = Int[i for i in 1:n]
	while l>0
		t = 0
		vst = zeros(Int,n)
		c = Int[]
		for i in b
			if !isempty(a[i])
				j = a[i][1]
				if !isempty(a[j])
					if a[j][1] == i
						if vst[i] == 0
							push!(c,i)
							vst[i] = 1
						end
						if vst[j] == 0
							push!(c,j)
							vst[j] = 1
						end
						t += 1
					end
				else
					f = 1
				end
			end
		end
		l -= length(c)
		if t>0
			k += 1
			for i in c
				if !isempty(a[i])
					shift!(a[i])
				end
			end
			b = copy(c)
		else
			f = 1
		end
		if f == 1
			break
		end
	end
	println(f==0?k:-1)
end

main()

Measured memory_bytes: 169360
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	int k, i;
	cin >> s >> k;
	for (i = 0; i < s.size(); i++) {
		if (s[i] == 'a') {
			continue;
		}
		if (s[i] + k > 'z') {
			k -= 'z' - s[i] + 1;
			s[i] = 'a';
		}
	}
	s[--i] = 'a' + (s[i] - 'a' + k) % ('z' - 'a' + 1);
	cout << s << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int N;
    cin >> N;
    ll S = 0, ans = 0, m = 1000000007;
    for (int i = 0; i < N; i++) {
        ll A;
        cin >> A;
        ans += S*A;
        S += A;
        S %= m, ans %= m;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3556
#include <iostream>
#include <algorithm>
#include <array>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vsort(x) sort(x.begin(),x.end())

using int64 = uint64_t;

using namespace std;
void solve(int x) {
	x = 1000 - x;
	int cnt = 0;
	int a[6] = { 500,100,50,10,5,1 };
	rep(i,0,6){
		while (x >= a[i]) {
			x -= a[i];
			cnt++;
		}
	}
	cout << cnt << endl;
}
int main() {

	int i, j, k;
	int n;
	cin >> n;
	while (n != 0) {
		solve(n);
		cin >> n;
	}
	return 0;
}

Measured memory_bytes: 2976
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  int N,K;
  cin >> N >> K;
  vector<int> a(N);
  for(int i=0; i<N; i++) cin >> a[i]; 
  int sum=0;
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(int i=0; i<K; i++) sum+=a[i];
  
  cout << sum << endl;
  
}

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

using namespace std;

int mem[100005];
int n,m;
vector<int> adj[100005];

int go(int x)
{
	if(mem[x]!=-1) return mem[x];
	mem[x]=0;
	for(int i:adj[x])
		mem[x]=max(mem[x],1+go(i));
	return mem[x];
}

int main()
{
	cin >> n >> m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin >> x >> y;
		adj[x].push_back(y);
	}
	int ans=0;
	memset(mem,-1,sizeof mem);
	for(int i=1;i<=n;i++) ans=max(ans,go(i));
	cout << ans << endl;
}

Measured memory_bytes: 7424
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a[100], b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  rep(i, 5) {
    cin >> b;
    if (b == 0) Cout(i + 1);
  }
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

  vector<int> prefs(M);
  vector<int> years(M);

  int p, d;
  for (int m = 0; m < M; m++) {
	cin >> p >> d;
	prefs[m] = p;
	years[m] = d;
  }

  vector<vector<int>> a(N, vector<int>(0));
  for (int i = 0; i < M; i++) {
	a[prefs[i]-1].push_back(years[i]);
  }

  for (int i = 0; i < N; i++) {
	sort(a[i].begin(), a[i].end());
  }

  for (int i = 0; i < M; i++) {

	string firstHalf = to_string(prefs[i]);
	string spaces = "";
	for (int j = firstHalf.size(); j < 6; j++) {
	  spaces += "0";
	}
	cout << spaces << firstHalf;



	auto itr = lower_bound(a[prefs[i]-1].begin(), a[prefs[i]-1].end(), years[i]);
	int x = itr - a[prefs[i]-1].begin() + 1;
	firstHalf = to_string(x);
	spaces = "";
	for (int j = firstHalf.size(); j < 6; j++) {
	  spaces += "0";
	}
	cout << spaces << firstHalf << endl;

  }


  return 0;
}


Measured memory_bytes: 7808
from sys import stdin
import sys
##  input functions for me
def ria(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    W = ria()
    s = sum(W)
    ans = s
    t = 0
    for i in range(N):
        t += W[i]
        s -= W[i]
        ans = min(ans, abs(s - t))
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	string A[100], sub1;
	int B[100], sub2, C[100], N;
	int i, j;
	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		C[i] = i + 1;
	}
	for (i = 0; i < N-1; i++) {
		for (j = i + 1; j < N; j++) {
			if (A[i] >= A[j]) {
				sub1 = A[i];
				A[i] = A[j];
				A[j] = sub1;
				sub2 = B[i];
				B[i] = B[j];
				B[j] = sub2;
				sub2 = C[i];
				C[i] = C[j];
				C[j] = sub2;
			}
		}
	}
	for (i = 0; i < N - 1; i++) {
		for (j = i + 1; j < N; j++) {
			if (A[i] == A[j]) {
				if (B[i] < B[j]) {
					sub1 = A[i];
					A[i] = A[j];
					A[j] = sub1;
					sub2 = B[i];
					B[i] = B[j];
					B[j] = sub2;
					sub2 = C[i];
					C[i] = C[j];
					C[j] = sub2;
				}
			}
		}
    }
	for (i = 0; i < N; i++)
		cout << C[i] << endl;
return 0;
}


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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const int    INF = 100000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

int N, M;
int x[11111], y[11111];
int s[11111][11111], t[11111][11111];
int tx;
char q;
int R;
int z[1111];
int dp[1111][222];

int main(int argc, char *argv[])
{
  while(cin >> N >> M, N){
    rep(i, N) rep(j, N) s[i][j] = t[i][j] = INF;
    rep(i, M){
      cin >> x[i] >> y[i] >> tx >> q;
      if(q == 'L') minup(s[x[i] - 1][y[i] - 1], tx);
      if(q == 'L') minup(s[y[i] - 1][x[i] - 1], tx);
      if(q == 'S') minup(t[x[i] - 1][y[i] - 1], tx);
      if(q == 'S') minup(t[y[i] - 1][x[i] - 1], tx);
    }
    cin >> R;
    rep(i, R) cin >> z[i];
    rep(i, R) z[i] -= 1;
    rep(i, N) s[i][i] = t[i][i] = 0;
    rep(k, N) rep(i, N) rep(j, N) minup(s[i][j], s[i][k] + s[k][j]);
    rep(k, N) rep(i, N) rep(j, N) minup(t[i][j], t[i][k] + t[k][j]);

    rep(i, R) rep(j, N) dp[i][j] = INF;
    rep(i, N) dp[0][i] = s[z[0]][i] + t[i][z[0]];
    rep(i, R - 1) rep(j, N) rep(k, N){
      minup(dp[i + 1][k], dp[i][j] + s[z[i]][j] + t[j][k] + s[k][z[i + 1]]);
      if(j == k) minup(dp[i + 1][k], dp[i][k] + s[z[i]][z[i + 1]]);
    }

    int res = INF;
    rep(i, N) minup(res, dp[R - 1][i]);
    cout << res << endl;
  }
  
  return 0;
}

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

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n+1), b(m+1);
    vector<ll> A(n+1), B(m+1);
    for(int i=1; i<=n; i++) {
        cin >> A[i];
        a[i] = a[i-1] + A[i];
    }
    for(int i=1; i<=m; i++) {
        cin >> B[i];
        b[i] = b[i-1] + B[i];
    }
    int j = m, ans = 0;
    for(int i=0; i<=n; i++) {
        if(a[i] > k) break;
        while(b[j] > k - a[i]) {
            j--;
        }
        ans = max(ans, i + j);
    }
    cout << ans << endl;
}

Measured memory_bytes: 9592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<t;i++)
#define MAXNUM 111111
int dset[MAXNUM];
int fa(int a)
{
    if(dset[a]!=a)return dset[a]=fa(dset[a]);
    return a;
}
int main()
{
    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    rep(i,1,n+1)dset[i]=i;
    rep(i,1,m+1)scanf("%d%d%d",&a,&b,&c),dset[fa(a)]=fa(b);
    int res=0;
    rep(i,1,n+1)res+=dset[i]==i;
    printf("%d\n",res);
}

Measured memory_bytes: 640
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,ll> type;
typedef pair<ll,type> event;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

int main(){
  int n,q; cin >> n >> q;
  vector<event> v;
  rep(i,n){
    int s,t,x; cin >> s >> t >> x;
    v.push_back({s-x,type(-1,x)}); //工事開始
    v.push_back({t-x,type(0,x)}); //工事終了
  }
  rep(i,q){
    int d; cin >> d;
    v.push_back({d,type(1,i)});//クエリ。valueには入力順を記録
  }
  sort(v.begin(),v.end());//イベントがスタートする順番に並べる
  
  vector<ll> res(q);
  multiset<ll> se;
  for(auto p:v){
    ll x = p.first; //時間
    int ty = p.second.first; //イベントタイプ
    ll val = p.second.second; //value
    if(ty == -1) se.insert(val); //開始イベントならsetに座標を突っ込む
    else if (ty == 0) se.erase(se.find(val)); //終了イベントならその座標のイベントを消す
    else res[val] = (se.empty() ? -1: *(se.begin())); //クエリイベントなら今の
  }
  for(auto v:res) cout << v << endl;
  return 0;
}

Measured memory_bytes: 28004
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
// Welcome to my source code!

const int MOD = 1000000007;

vector<ll> pf(ll n) {
    vector<ll> p;
    double x = sqrt(n);
    for (ll i = 2; i <= x; i++) {
        while (n % i == 0 && n) {
            p.push_back(i);
            n /= i;
        }
    }
    if (n != 1) p.push_back(n);
    return p;
}

vector<ll> divisors(ll n) {
    vector<ll> div;
    double x = sqrt(n);
    for (ll i = 1; i <= x; i++) {
        if (n % i == 0) {
            div.push_back(i);
            if (i != n / i) div.push_back(n / i);
        }
    }
    sort(div.begin(), div.end());
    return div;
}

int main() {
    int n;
    cin >> n;
    ll d[n + 1] = {};
    for (int i = n; i >= 1; i--) {
        vector<ll> vec = divisors(i);
        for (auto x : vec) d[x]++;
    }
    ll prime[n + 1] = {};
    for (int i = 2; i <= n; i++) {
        if (d[i]) {
            vector<ll> vec = pf(i);
            for (auto x : vec) {
                prime[x]++;
            }
        }
    }
    ll ans = 1;
    for (int i = 2; i <= n; i++) {
        if (prime[i]) ans *= (prime[i] + 1);
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
typedef struct{char c;int n;} card;
card B[36],S[36];
int bubble(card A[36],int N)
{
    int i,j,c=0;
    card stock;
    for(i=0;i<N;i++){
        for(j=N-1;j>0;j--){
            if(A[j].n<A[j-1].n)
            {
                stock=A[j];
                A[j]=A[j-1];
                A[j-1]=stock;
                c++;
            }       
        }
    }
    return c;
}
int selection(card A[36],int N)
{
    int i,j,d,minj,c=0;
    card stock;
    for(i=0;i<N;i++)
    {
        minj=i;
        for(d=0,j=i;j<N;j++)
        {
            if(A[j].n<A[minj].n){minj=j;d=1;}
        }
        stock=A[i];
        A[i]=A[minj];
        A[minj]=stock;
        if(d)c++;
    }
    return c;
}
int main(void)
{
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
      scanf(" %c%d",&B[i].c,&B[i].n);
    }
    memcpy(S,B,sizeof(B));
    bubble(B,n);
    selection(S,n);
    for(i=0;i<n;i++)
    {
        printf("%c%d",B[i].c,B[i].n);
        if(i<n-1){
	  printf(" ");
	}
        else{
	  printf("\n");
	}
    }
    printf("Stable\n");
    for(i=0;i<n;i++)
    {
        printf("%c%d",S[i].c,S[i].n);
        if(i<n-1){
	  printf(" ");
	}
        else{
	  printf("\n");
	}
    }
    if(!memcmp(B,S,sizeof(B))){
      printf("Stable\n");
    }
    else{
      printf("Not stable\n");
    }
 
    return 0;
}



Measured memory_bytes: 2132
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 1000000009

ll min(ll a,ll b,ll c,ll d){
  if(a < b && a < c && a < d)
    return a;
  else if(b < a && b < c && b < d)
    return b;
  else if(c < a && c < b && c < d)
    return c;
  else
    return d;
}

ll min(ll a,ll b,ll c){
  if(a < b && a < c)
    return a;
  else if(b < a && b < c)
    return b;
  else 
    return c;
}

int main(){
  ll q,h,s,d;
  cin >> q >> h >> s >> d;
  ll n;
  cin >> n;
  ll ans = 0;
  ll qq = 8*q;
  ll hh = 4*h;
  ll ss = 2*s;
  ll firstkey = min(qq,hh,ss,d);
  ll firstans = 0;
  if(firstkey == qq) firstans = q;
  else if(firstkey == hh) firstans = h;
  else if(firstkey == ss) firstans = s;
  else firstans = d;
  ll nn = n / 2;
  ll nnn = n % 2;
  //cout << firstkey << " " << firstans << endl;
  ans += firstkey*nn;
  ll qqq = 4*q;
  ll hhh = 2*h;
  ll secondkey = min(qqq,hhh,s);
  ll secondans = 0;
  if(secondkey == qqq) secondans = q;
  else if(secondkey == hhh) secondans = h;
  else secondans = s;
  //cout << secondkey << " " << secondans << endl;
  ans += secondkey*nnn;
  cout << ans << endl;


}


Measured memory_bytes: 256
n = int(input())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
CD = []
for i in range(n):
    c, d = map(int, input().split())
    CD.append((c, d))

AB.sort(key=lambda x:-x[1])
CD.sort()

#print(AB)
#print(CD)

ans = 0
used = set()
for i in range(n):
    c, d = CD[i]
    for j in range(n):
        if j in used:
            continue
        a, b = AB[j]
        if a < c and b < d:
            ans += 1
            used.add(j)
            break
print(ans)


Measured memory_bytes: 66852
#[(素因数, 指数)]の2次元リスト(1を含まない)

def factorize(n):
	arr = []
	temp = n
	
	for i in range(2, int(n**0.5)+1):
		if temp % i == 0:
			count = 0
			while temp % i == 0:
				count += 1
				temp //= i
			arr.append([i, count])
	
	if temp != 1:
		arr.append([temp, 1])
	
	if arr == []:
		arr.append([n, 1])
	
	return arr

N = int(input())
if N == 1:
    print(0)
else:
    L = factorize(N)
    count = 0
    for a in L:
        i = 1
        while True:
            a[1] = a[1] - i
            if a[1] < 0:
                break
            else:
                count += 1
                i += 1
    print(count)

Measured memory_bytes: 9488
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    n, m, x = map(int, input().split())
    data = np.array(read().split(), np.int64)
    data = data.reshape(n, -1) # dataをn行に整形
    cost_per_cost = data[:, 0] # data全行の0列
    effect_per_book = data[:, 1:]

    costs = np.zeros(2**n, np.int64)
    # ability 行数：2**n(本の組み合わせパターン), 列数：アルゴリズムの数
    ability = np.zeros((2**n, m), np.int64)
    for i in range(n):
        costs[1<<i:1<<(i+1)] = costs[:1<<i] + cost_per_cost[i]
        ability[1<<i:1<<(i+1)] = ability[:1<<i] + effect_per_book[i]
    ok = np.all(ability >= x, axis=1)
    res = costs[ok]
    if len(res) == 0:
        print(-1)
    else:
        print(res.min())

if __name__ == '__main__':
    main()



Measured memory_bytes: 27656
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <complex>
#include <bitset>
#define full(c) c.begin(), c.end()
#define vector2d(name,type,h,w,init) vector<vector<type>> name(h,vector<type>(w,init)) 
const int PRIME = 1000000007;
const int INT_INF = 2147483647;
const long long int LL_INF = 9223372036854775807;
const double PI = acos(-1);
const double EPS = 0.000000001;
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;

int main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	ll i, n;
	cin >> n;
	vector<ll> x(n + 2);
	vector<ll> first(n + 2);
	vector<ll> second(n + 2);
	x[0] = 0;
	for (i = 1; i <= n; i++) cin >> x[i];
	x[n + 1] = 0;
	first[0] = 0;
	for (i = 1; i < n + 2; i++){
		first[i] = first[i - 1] + abs(x[i] - x[i - 1]);
	}
	second[n + 1] = 0;
	for (i = n; i >= 0; i--){
		second[i] = second[i + 1] + abs(x[i] - x[i + 1]);
	}
	for (i = 1; i < n + 1; i++){
		cout << first[i - 1] + abs(x[i - 1] - x[i + 1]) + second[i + 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 3584
//@sakshjha
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define ld long double
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FRE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define pi 3.14159265358979
const ll MOD = 1000000007;
const ll N=200005;
int main()
{
    IOS
    ll n,k,j;
    cin>>n>>k;
    ll a[n],i,dp[n];
    for(i=0; i<n; i++)
    {
        cin>>a[i];
    }
    dp[0]=0;
    for(i=1; i<n; i++)
    {
        dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
        for(j=2; j<=k; j++)
        {
            if(i-j<0)
                break;
            else
                dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
        }
    }
    cout<<dp[n-1];
    return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 998244353;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin >> n;
  vll d(n);
  REP(i, n)
    cin >> d[i];

  vll rank(n, 0);
  REP(i, n){
    rank[d[i]]++;
  }

  ll ans = 1;
  if(rank[0] != 1 || d[0] != 0)
    ans = 0;

  REP1(i, n){
    REP(j, rank[i]){
    ans *= rank[i-1];
    ans %= MOD;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=2147483647;
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m,x,flag,ans=INF,Pow[13],a[13],b[13][13],c[13];
int main(){
	n=read(),m=read(),x=read();
	Pow[0]=1;
	for(int i=1;i<=13;i++) Pow[i]=Pow[i-1]<<1;
	for(int i=0;i<n;i++){
		a[i]=read();
		for(int j=0;j<m;j++) b[i][j]=read();
	}
	for(int i=0;i<Pow[n];i++){
		memset(c,0,sizeof(c));
		int sum=0;
		for(int j=0;j<n;j++){
			if(i&Pow[j]){
				sum+=a[j];
				for(int k=0;k<m;k++) c[k]+=b[j][k];
			}
		}
		flag=1;
		for(int j=0;j<m;j++){
			if(c[j]<x){
				flag=0;
				break;
			}
		}
		if(flag) ans=min(ans,sum);
	}
	if(ans==INF) printf("-1\n");
	else printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3748
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#define FOR(i,a,n) for(i=(a);i<(n);i++)
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define LOCAL
#ifdef LOCAL
    #define DEBUG(...) printf(" "__VA_ARGS__)
#else
    #define DEBUG(...)
#endif /* LOCAL */
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}

char str[30];
int cnt[26];
int main(void)
{
	int len,i,j;
	scanf("%s",str);
	len=strlen(str);
	FOR(i,0,len) cnt[str[i]-'a']++;
	if(len<26){
		for(i=0;cnt[i];i++);
		str[len]='a'+i;
		puts(str);
		return 0;
	}else{
		for(i=len-1;i>=0;i--){
			for(j=(str[i]-'a');j<26;j++){
				if(!cnt[j]){
					str[i]='a'+j;
					puts(str);
					return 0;
				}
			}
			cnt[str[i]-'a']=0;
			str[i]='\0';
		}
	}
	puts("-1");
	return 0;
}
    
    


Measured memory_bytes: 128
n=int(input())
h=list(map(int,input().split()))
dp=[0]*(n+10)
dp[0]=0
dp[1]=abs(h[1]-h[0])
ans=0
for i in range(n-2):
  dp[i+2]=min(dp[i]+abs(h[i+2]-h[i]),dp[i+1]+abs(h[i+2]-h[i+1]))
print(dp[n-1])

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

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

#ifdef LOCAL
#define i64 "%lld"
#else
#define i64 "%I64d"
#endif

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

string s;

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

    cin >> s;
    int a = -1, b = -1;
    forsn(i,1,si(s)) {
        if (s[i-1] == s[i]) {
            a = i; b = i+1;
            break;
        }
        if (i > 1 && s[i-2] == s[i]) {
            a = i-1; b = i+1;
            break;
        }
    }
    cout << a << ' ' << b << endl;

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

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

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 1000000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
  int N;
  while(cin>>N && N){
    int hp[100];
    REP(i, N) cin>>hp[i];
    int M; cin>>M;
    int mp[100], pow[100], type[100];
    REP(i, M){
      string s; cin>>s;
      cin>>mp[i];
      cin>>s;
      if(s == "Single") type[i] = 0;
      else type[i] = 1;
      cin>>pow[i];
    }
    ll dp[2][100001];
    REP(i, 2) fill(dp[i], dp[i] + 100001, 1e16);
    dp[0][0] = 0, dp[1][0] = 0;
    REP(from, 100000){
      REP(i, M){
        int to = from + pow[i];
        if(to > 100000) to = 100000;
        dp[type[i]][to] = min(dp[type[i]][to], dp[type[i]][from] + mp[i]);
      }
    }
    REP(i, 2) for(int j = 100000; j > 0; j--) dp[i][j - 1] = min(dp[i][j - 1], dp[i][j]);
    ll ans = 1e16;
    REP(all, 100001){
      ll sub_ans = dp[1][all];
      REP(i, N){
        if(hp[i] - all > 0){
          sub_ans += dp[0][hp[i] - all];
        }
      }
      ans = min(ans, sub_ans);
    }
    cout<<ans<<endl;
  }

  return 0;
}

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

int main()
{

        string s;
        cin >> s;

        int len = s.length();

        bool ans = false;
        for (int i = 0; i < len; i+=2) {
                if (s[i] == 'h' && s[i+1] == 'i') {

                }
                else {
                        cout << "No" << endl;
                        return 0;
                }
        }
        cout << "Yes" << endl;
}


Measured memory_bytes: 256
main = do
    s <- getLine
    putStrLn $ show $ min (solve '0' s) (solve '1' s)

solve _ [] = 0
solve b (a:as)
    | b == a = solve (fl b) as
    | otherwise = 1 + solve (fl b) as

fl '0' = '1'
fl _ = '0'

Measured memory_bytes: 7548
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int ans = 0;
  for(int i=0; i<S.size(); i++){
    ans += S[i] - '0';
  }
  if(ans %9 == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3664
import math
n = int(raw_input())
for i in range(n):
    x1, y1, x2, y2, x3, y3 = map(float, raw_input().split())
    a = math.sqrt((x1-x2)**2+(y1-y2)**2)
    b = math.sqrt((x1-x3)**2+(y1-y3)**2)
    c = math.sqrt((x2-x3)**2+(y2-y3)**2)
    s = (a+b+c)/2
    ss = math.sqrt(s*(s-a)*(s-b)*(s-c))
    sina = 2*ss/b/c
 
    r = a/sina/2

    a = a*a
    b = b*b
    c = c*c
    px = (a*(b+c-a)*x3 + b*(a+c-b)*x2+c*(a+b-c)*x1)/16/ss**2
    py =(a*(b+c-a)*y3 + b*(a+c-b)*y2+c*(a+b-c)*y1)/16/ss**2

    print "%.3f %.3f %.3f" % (px, py, r)

Measured memory_bytes: 4444
import java.util.ArrayList;
import java.util.Scanner;
class Main{


	static final int MOD = 1000000007;


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		String ss = sc.next();
		String mae = ss.substring(0,ss.length()/2);
		String ushiro = ss.substring(ss.length()/2);
		if(mae.equals(ushiro)){
			System.out.println("Yes");

		}else{
			System.out.println("No");

		}

		


		




	}

	static void sieve(ArrayList<Long> list){
		int n = 50000000;
		boolean[] is_prime = new boolean[n+1];
		int[] prime = new int[n];
		for(int i= 0;i <=n;i++){
			is_prime[i] = true;
		}
		list.add((long) 1);
		for(int i = 2;i <= n;i++){
			if(is_prime[i]){
				list.add((long)i);
				for(int j = 2*i;j <= n;j+=i){
					is_prime[j] = false;
				}
			}
		}



	}




	static int upperbond(int k,int min,int[] data){		//kより小さい最大の値をdataの中から探し、返す二分探索
		int max = data.length;
		//		if(min == data.length-1){
		//			if(data[min] > k){
		//				return min;
		//			}
		//		}

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}

		return max;
	}

	static int lowerbond(int k,int min,int[] data){		//kより大きい最小の値をdataの中から探し、返す二分探索
		int max = data.length;

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}
		return min;
	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}


class Edge extends ArrayList<P>{

}

class P{
	int to;
	long cost;
	P(int to,long cost){
		this.to = to;
		this.cost = cost;
	}
}


class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return   from- otherpair.from;
	}








}






Measured memory_bytes: 21972
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>

using namespace std;

int m,n,k,card[200],kari[200];

int main(){
	cin>>n>>m;
	for(int i=0;i<2*n;i++){
		card[i]=i+1;
		kari[i]=i+1;
	}
	for(int i=0;i<m;i++){
		cin>>k;
		if(k==0){
			for(int j=0;j<n;j++){
				card[2*j]=kari[j];
				card[2*j+1]=kari[j+n];
			}
		}else{			
			for(int j=2*n-k;j<2*n;j++){card[j]=kari[j-(2*n-k)];}
			for(int j=0;j<2*n-k;j++){card[j]=kari[j+k];}
		}
		for(int j=0;j<2*n;j++){kari[j]=card[j];}
	}
	for(int i=0;i<2*n;i++){
		cout<<card[i]<<endl;
	}
	cin>>m;
		
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

#define MAX_V 200000

long long int INF = 100000000000000000LL;

struct edge{
	int to;
	long long int cost;
};

typedef pair<long long int, int> P; // firstは最短距離、secondは頂点の番号

vector<edge> G[MAX_V];
long long int d[MAX_V];
long long int H[200000];
long long int X;

// 速さはO(|E|log|V|)

void shortest_path(int s, int V){ // Vは頂点数
	
	priority_queue<P, vector<P>, greater<P> > que;
	
	for(int i = 0; i < V; i++){
		d[i] = INF;
	}
	d[s] = 0;
	
	que.push(P(0, s));
	
	while(!que.empty()){
		
		P p = que.top();
		que.pop();
		
		int v = p.second;
		
		if(d[v] < p.first){
			continue;
		}
		
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > max(e.cost + d[v], X - H[e.to])){
				d[e.to] = max(e.cost + d[v], X - H[e.to]);
				que.push(P(d[e.to], e.to));
			}
		} // 頂点への最小コストを更新
	}
}

int main(){
	
	int N, M;
	
	cin >> N >> M >> X;
	
	for(int i = 0; i < N; i++){
		cin >> H[i];
	}
	
	for(int i = 0; i < M; i++){
		edge e1, e2;
		long long int index1, index2, cost;
		cin >> index1 >> index2 >> cost;
		index1--;
		index2--;
		e1.to = index2;
		e2.to = index1;
		e1.cost = cost;
		e2.cost = cost;
		if(cost <= H[index1]){
			G[index1].push_back(e1);
		}
		if(cost <= H[index2]){
			G[index2].push_back(e2);
		}
	}
	
	shortest_path(0, N);
	
	/*
	for(int i = 0; i < N; i++){
		cout << d[i] << endl;
	}
	*/
	
	if(d[N - 1] == INF){
		cout << "-1" << endl;
		return 0;
	}
	
	cout << 2 * d[N - 1] + H[N - 1] - X << endl;
	
	return 0;
}



Measured memory_bytes: 24884
import collections


Point = collections.namedtuple('Sushi', ['position', 'value'])


def read_ints():
    return map(int, input().split())


def reverse_points(points, length):
    return [Point(length - p.position, p.value) for p in reversed(points)]


def solve_unidir(points, length):
    forward_peaks = [(-1, 0)]
    forward_accumulated_value = 0
    for i, p in enumerate(points):
        forward_accumulated_value += p.value
        forward_actual_value = forward_accumulated_value - p.position
        if forward_actual_value > forward_peaks[-1][1]:
            forward_peaks.append((i, forward_actual_value))
    best_value = forward_peaks[-1][1]
    backward_accumulated_value = 0
    for i, p in reversed(list(enumerate(points))):
        while forward_peaks[-1][0] >= i:
            forward_peaks.pop()
        backward_accumulated_value += p.value
        backward_actual_value = backward_accumulated_value - 2 * (length - p.position)
        best_value = max(best_value, backward_actual_value + forward_peaks[-1][1])
    return best_value


def solve(points, length):
    return max(solve_unidir(points, length),
               solve_unidir(reverse_points(points, length), length))


def main():
    n, length = read_ints()
    points = []
    for _ in range(n):
        position, value = read_ints()
        points.append(Point(position, value))
    print(solve(points, length))


if __name__ == '__main__':
    main()


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

int main(){
    //入力
    int n; cin >> n;
    long long a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    //Ai+Aj=i-jより、i-Ai=j+Aj。左辺と右辺それぞれの値を全ての参加者についてもとめその値をkeyとした連想配列で求める

    //和と差を保管する連想配列
    map<long long, long long>plus;
    map<long long, long long>minus;

    
    for (int i = 0; i < n; i++)
    {
        plus[i + 1 + a[i]] += 1;
        minus[i + 1 - a[i]] += 1;
    }

    //ペアの数カウント変数
    long long count = 0;

    //i-Ai=j+Ajが成り立つ時の両辺の値の範囲は大体0〜nである
    for (int i = 0; i <= n; i++)
    {
        count += plus[i] * minus[i];
    }

    cout << count << endl;
    
}

Measured memory_bytes: 47996
count = 0
def mergesort(A, left, right):
    if left + 1 < right:
        mid = (left + right)/2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    global count
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(float("inf"))
    R.append(float("inf"))
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        




if __name__ == "__main__":
    num = int(raw_input())
    num_list = raw_input().strip().split()
    num_list = map(int, num_list)
    mergesort(num_list, 0, len(num_list))
    num_list = map(str, num_list)
    print " ".join(num_list)
    print count

Measured memory_bytes: 70424
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<ll> q;
	vector<ll> x;	
	for( int i = 0; i < n; ++i ){
		ll temp;
		cin >> temp;
		q.push_back(temp);
		x.push_back(temp);
	}
	sort(x.begin(), x.end());
	ll l = x.at(n/2-1);
	ll r = x.at(n/2);
	for( ll i : q ){
		cout << ( ( i <= l ) ? r : l ) << endl;
	}
	return 0;
}

Measured memory_bytes: 5476
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<limits>
#include<iomanip>
#include<cmath>
#include<climits>
using namespace std;

typedef long long ll;
typedef string S;
typedef pair<int,int> P;
typedef vector<int> vi;
const int mod=1e9+7;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[3],b[3];
    int num[4]={0,0,0,0};
    for(int i=0;i<3;i++){
        cin >> a[i] >> b[i];
        num[a[i]-1]++;
        num[b[i]-1]++;
    }
    cout << (num[0]<=2&&num[1]<=2&&num[2]<=2&&num[3]<=2?"YES":"NO") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define chmax(a,b) if(a<b)a=b;
#define chmin(a,b) if(b<a)a=b;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
constexpr bool isPrime(int x) {
	if(x == 2 || x == 3) return true;
	else if(x < 2 || x % 2 == 0 || x % 3 == 0) return false;
	int s = sqrt(x) + 1;
	for(int i = 5; i <= s; i += 2) {
		if(x % i == 0) return false;
	}
	return true;
}
int main() {
	int n; cin >> n;
	int x, cnt = 0;
	rep(i, 0, n) {
		cin >> x;
		if(isPrime(x)) ++cnt;
	}
	P(cnt);
	return 0;
}

Measured memory_bytes: 3128
from sys import stdin
from collections import deque


def get_adj_list(num_nodes, data, undirected=True):
    # adj_list ex) {1:[2,3,4], 2:[1,4,5], 3:[1,4], 4:[1,2,3,5], 5:[2,4]}
    graph = {}
    for i in range(num_nodes):
        graph[i+1] = []
    for val in data:
        x, y = val
        graph[x] = graph[x] + [y]
        if undirected:
            graph[y] = graph[y] + [x]
    return graph


def breadth_first_search(adj_list, start_node):
    dist = {}
    queue = deque([(start_node, 0)])
    while len(queue) > 0:
        v, d = queue.popleft()
        if v in dist: continue
        dist[v] = d
        for u in adj_list[v]:
            if u not in dist:
                queue.append((u, d+1))
    return dist

# bfs
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        dist = breadth_first_search(adj_list, i+1)
        for j in range(i, N):
            dist_cnt[dist[j+1]] += 1
    for i in range(1, N):
        print(dist_cnt[i])

# 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Measured memory_bytes: 80220
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int X, Y, Z, i;
    cin >> X >> Y >> Z;
    for (i = 1; i < 100000; i++){
      if (X < Y * i + Z * (i + 1)){
        cout << (i - 1)<< endl;
        break;
      }
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int a, b;

  scanf("%d%d", &a, &b);

  if (a < b) printf("a < b\n");

  if (a > b) printf("a > b\n");

  if (a == b) printf("a == b\n");

  return 0;
}
   

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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int N;
  cin >> N;
  while (N > 10) {
    N %= 10;
  }

  if (N == 3) {
    cout << "bon" << endl;
  } else if (N == 0 || N == 1 || N == 6 || N == 8) {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }

  return 0;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

const double pie = acos(-1.0);

// 最大公約数
ll gcd(ll a, ll b)
{
   if (a%b == 0) {
       return(b);
   } else {
       return(gcd(b, a%b));
   }
}

// 最小公倍数
ll lcm(ll a, ll b){
   return a * b / gcd(a, b);
}

//素数判定
bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(unsigned i = 5; i * i <= n; i += 6) {
        if(n % i     == 0) return false; // (6の倍数)-1
        if(n % (i+2) == 0) return false; // (6の倍数)+1
    }
    return true;
}

void solve() {
    ll n; cin >> n;
    ll m=0,a=0,r=0,c=0,h=0;
    rep(i, 0, n){
        string s; cin >> s;
        if(s[0] == 'M') m++;
        if(s[0] == 'A') a++;
        if(s[0] == 'R') r++;
        if(s[0] == 'C') c++;
        if(s[0] == 'H') h++;
    }
    cout << m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h +
    + a*r*c + a*r*h + a*c*h + r*c*h << endl;
}

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

    solve();
    return 0;
}


Measured memory_bytes: 256