akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

#define MAX_N (100000L)

int main(int argc, char *argv[]) {
  // read inputs
  long N, as[MAX_N];
  scanf("%ld", &N);
  for (long i = 0; i < N; i++) {
    scanf("%ld", &as[i]);
  }

  // solve
  long xs[MAX_N];
  // calculate x1
  xs[0] = 0;
  for (long i = N - 1; i >= 0; i--) {
    xs[0] += i % 2 ? -as[i] : as[i];
  }
  // calculate rest
  for (long i = 1; i < N; i++) {
    xs[i] = 2 * as[i - 1] - xs[i - 1];
  }

  // print answer
  for (long i = 0; i < N; i++) {
    printf("%ld ", xs[i]);
  }
  printf("\n");

  return 0;
}


Measured memory_bytes: 2816
#include<stdio.h>
#include<climits>

int k = 0;

void Merge(long* a, int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	long* L = new long[n1+1];
	long* R = new long[n2+1];
	for ( int i = 0; i < n1; i++) L[i] = a[left + i];
	L[n1] = LONG_MAX;
	for (int i = 0; i < n2; i++) R[i] = a[mid + i];
	R[n2] = LONG_MAX;
	int i = 0;
	int j = 0;
	while(i < n1 || j < n2){
		if (L[i] <= R[j]){
			a[left + i + j] = L[i];
			i++;
			k++;
		}
		else{
			a[left + i + j] = R[j];
			j++;
			k++;
		}
	}
}

void MergeSort(long* a, int left, int right){
	if (left + 1 < right){
		int mid = (left + right) / 2;
		MergeSort(a, left, mid);
		MergeSort(a, mid, right);
		Merge(a, left, mid, right);
	}
}

int main(){
	int n = 0;
	scanf("%d", &n);
	long* a = new long[n];
	for (int i = 0; i < n; i++) scanf("%ld", &a[i]);
	MergeSort(a, 0, n);
	for ( int i = 0; i < n; i++){
		printf("%ld", a[i]);
		if (i != n-1) printf(" ");
	}
	printf("\n");
	printf("%d\n", k);
}


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

int main(){
    long long n;
    cin>>n;
    map<long long,long long> checklist;
    long long a;
    long long Ai;
    long long Aj;
    long long cnt=0;
    for(long long i=1;i<=n;i++){
        cin>>a;
        Ai=a+i;
        Aj=i-a;
        if(checklist.count(Aj)!=0){
            cnt+=checklist[Aj];
        }
        if(checklist.count(Ai)==0){
            checklist.insert(make_pair(Ai,1));
        }else{
            checklist[Ai]+=1;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 16076
import itertools
s = str(input())

lst = [i for i in itertools.product([0,1],repeat = len(s) - 1)]
s4  = []
for l in lst:
    s3 = list(s)
    h = 0
    for i in range(0, len(s)-1):
        if l[i] == 1:
            s3.insert(i+h+1,'+')
            h += 1
    s4.append(s3)
print(sum([eval(''.join(i)) for i in s4]))

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


int min_element(vector<int> v, int size){
	int ret = v.at(0);
	for(int i=0;i<size;i++){
		ret = min(ret, v.at(i));
	}
	return ret;
}


int main(){
	int  N, M, X;
	cin >> N >> M >> X;
	vector<vector<int>> A(N, vector<int>(M));
	vector<int> C(N);
	for(int i=0;i<N;i++){
		cin >> C.at(i);
		for(int j=0;j<M;j++){
			cin >> A.at(i).at(j);
		}
	}
	// bit zen-tan-saku
	int min_cost;
	bool first_cost = true;
	bool rikai_state = false;
	for(int tmp=0; tmp < (1 << N); tmp++){
		bitset<12> choose_C(tmp);
		int cost = 0;
		vector<int> rikaido(M);
		for(int i=0;i<N;i++){
			if(choose_C.test(i)){
				cost += C.at(i);
				for(int j=0;j<M;j++){
					rikaido.at(j) += A.at(i).at(j);
				}
			}
		}
		if(min_element(rikaido, M) >= X){
			rikai_state = true;
			if(first_cost){
				min_cost = cost;
				first_cost = false;
			}else{
				min_cost = min(min_cost, cost);
			}
		}
	}

	if(rikai_state){
		cout << min_cost << endl;
	}else{
		cout << -1 << endl;
	}

	return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<algorithm>
#include<vector>
int main() {
	int a, b, c;
	int g = 0;
	std::cin >> a >> b >> c;
	for (int i = a; i <= b; ++i) {
		if (c%i == 0)++g;
	}
	std::cout<<g<<std::endl;
	return 0;
}

Measured memory_bytes: 1164
/******************************************
* AUTHOR : SHUBHAM KUMAR *
* NICK : { "CODECHEF" : "SCHELEON",
           "CODEFORCES" : "SCH3130N" } *     
* INSTITUTION : BIT MESRA *
******************************************/
 
#include "bits/stdc++.h"
 
using namespace std;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define sd(x) scanf("%lld",&x)
#define pds(x) printf("%lld ", x)
#define large 100005
#define MOD 1000000007
#define dd double
#define pb push_back
#define mk make_pair
#define rep0(i,b) for(int i=0;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define pll pair<ll, ll>
#define ld long double
#define vll vector<ll>
#define vpll vector<pll>
#define sortv(v) sort(v.begin(),v.end())  
 
template <typename T> void max_self(T& a, T b) {
    a = max(a, b);
}
 
using ll = long long int;
using ull = unsigned long long int;
 
ll ModE(ll x, ull y, ll p = MOD) 
{ 
    ll res = 1;
    x = x % p;    
    while (y > 0) 
    {   if (y & 1) 
            res = (res*x) % p; 
        y = y>>1;
        x = (x*x) % p;   
    } 
    return res; 
}
 
 
 
int main() {
    #ifdef M_DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
 
    fastio
    ll n,k;
    cin>>n>>k;
    ll a[n];
    rep0(i, n)
        cin>>a[i];
    vector<bool> dp(k+1, false);
    dp[0]=false;
    rep1(ii, k)
        for(auto jj : a)
            if(ii >= jj && !dp[ii - jj])
                dp[ii] = true;
    if(dp[k])
        cout<<"First";
    else
        cout<<"Second";
    return 0;
}

Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()

total = 0
cnt = 0

while total < N:
    cnt += 1
    total += cnt

for i in range(1, cnt + 1):
    if i != total - N:
        print(i)

Measured memory_bytes: 83840
S=str(input())
ans='Yes'
for i in range(len(S)):
    if  (i+1)%2==0 and S[i] in ['L','U','D']:
        pass
    elif  (i+1)%2==1 and S[i] in ['R','U','D']:
        pass
    else:
        ans='No'
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;
int main(){
    ll h,w;cin>>h>>w;
    vector<vector<char>> v(h, vector<char> (w));
    REP(i,h){
        REP(j,w){
            cin>>v[i][j];
        }
    }
    vector<ll> line, column;
    REP(i,h){
        REP(j,w){
            if(v[i][j]=='#'){
                line.push_back(i);
                break;
            }
        }
    }
    REP(i,w){
        REP(j,h){
            if(v[j][i]=='#'){
                column.push_back(i);
                break;
            }
        }
    }
    ll l=SIZE(line), c=SIZE(column);
    REP(i,l){
        ll a=line[i];
        REP(j,c){
            ll b=column[j];
            cout<<v[a][b];
            if(j==c-1){
                cout<<endl;
            }
        }
    }
    return 0;
}


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

int main() {
	int N;
	cin >> N;
	vector<ll> A(N);
	for(auto &a : A) cin >> a;
	vector<ll> sum(N+1, 0);
	for(int i=1;i<=N;i++) sum[i] = sum[i-1] + A[i-1];

	ll ans = LLONG_MAX;
	// i番目のあとが真ん中の切れ目
	for(ll i=0;i<=N;i++) {
		// P, Qが一番近くなる切れ目を求める
		int low = 0, high = i;
		while(high - low > 1) {
			int mid = (high + low) >> 1;
			if(sum[mid] >= sum[i] - sum[mid]) high = mid;
			else low = mid;
		}
		ll P = sum[low], Q = sum[i] - sum[low];
		ll P2 = sum[high], Q2 = sum[i] - sum[high];
		ll left_min = min(P,Q), left_max = max(P,Q);
		if(llabs(P2-Q2) < llabs(P-Q)) {
			left_min = min(P2, Q2);
			left_max = max(P2, Q2);
		}

		// R, Sが一番近くなる切れ目を求める
		low = i+1, high = N;
		while(high - low > 1) {
			int mid = (high + low) >> 1;
			if(sum[mid] - sum[i] >= sum[N] - sum[mid]) high = mid;
			else low = mid;
		}
		ll R = sum[low] - sum[i], S = sum[N] - sum[low];
		ll R2 = sum[high] - sum[i], S2 = sum[N] - sum[high];
		ll right_min = min(R, S), right_max = max(R, S);
		if(llabs(R2-S2) < llabs(R-S)) {
			right_min = min(R2, S2);
			right_max = max(R2, S2);
		}

		ll tmp = max(left_max, right_max) - min(left_min, right_min);
		ans = min(ans, tmp);
	}
	cout << ans << endl;
}

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

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

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

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

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

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

const lli INF = 0xFFFFFFFFFFFFFFFL;

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

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

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

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

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

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

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a,e[maxN+5];
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

lli dfs(lli u,lli p)
{
    if(sz(e[u])==1)
        return a[u];

    lli cnt=0,mx=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        lli v=dfs(x,u);
        mx=max(mx,v);
        cnt+=v;
    }

    lli x=cnt-a[u];

    if(x<0||cnt/2<x)
    {
        cout<<"NO"<<endl;
        exit(0);
    }

    if(cnt<2*mx&&cnt-mx<x)
    {
        cout<<"NO"<<endl;
        exit(0);
    }

    dbg(u,2*a[u]-cnt)
    return 2*a[u]-cnt;
}

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

    cin>>n;
    a.clear();a.reserve(n+1);
    a.pb(0);
    fo(i,n)
    {
        cin>>in;
        a.pb(in);
    }

    if(n==2)
    {
        cout<<(a[1]==a[2]?"YES":"NO")<<endl;
        return 0;
    }

    fo(i,n-1)
    {
        cin>>u>>v;
        e[u].pb(v);
        e[v].pb(u);
    }

    repA(i,1,n)
    {
        if(sz(e[i])>1)
        {
            if(dfs(i,-1))
            {
                cout<<"NO"<<endl;
                exit(0);
            }
            break;
        }
    }

    cout<<"YES"<<endl;
}   aryanc403();
    return 0;
}


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

int main(){
    int n,m;
    cin>>n>>m;
    int p[100000],y[100000];
    vector<int> v[100001];
    for(int i=0;i<m;i++){
        cin>>p[i]>>y[i];
        v[p[i]].push_back(y[i]);
    }
    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(int i=0;i<m;i++){
        cout<<setfill('0')<<setw(6)<<p[i];
        cout<<setfill('0')<<setw(6);
        cout<<lower_bound(v[p[i]].begin(),v[p[i]].end(),y[i])-v[p[i]].begin()+1<<endl;
    }
}


Measured memory_bytes: 7808
using System;

namespace AtCoder
{
    static class Program
    {
        static void Main()
        {
            string[] nbrs = Console.ReadLine().Split();

            int nbr = int.Parse(nbrs[0] + nbrs[1]);
            double sqrt = Math.Sqrt(nbr);

            if (sqrt % 1 == 0)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define N 4050
#define c 2010
#define mod 1000000007
using namespace std;
typedef long long LL;
int n,a[50*N],b[50*N],F[N][N],jc[5*N];
inline int rd() {
    int x=0,f=1;char ch=getchar();
    while (ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

inline void inc(int &x,int y) {x=(x+y)%mod;}

inline int qp(int a,int b) {
    int ret = 1;
    while (b) {
        if (b&1) ret = 1LL * ret * a % mod;
        b >>= 1, a = 1LL * a * a % mod;
    }
    return ret;
}

inline int C(int a,int b) {
    return 1LL * jc[a] * qp(jc[b], mod-2) % mod * qp(jc[a-b], mod-2) % mod;
}

int main() {
    n = rd();
    for (int _=1;_<=n;_++) a[_] = rd(), b[_] = rd();

    for (int _=1;_<=n;_++) F[c-a[_]][c-b[_]]++;
    for (int x=c-2000;x<=c+2000;x++)
        for (int y=c-2000;y<=c+2000;y++)
            inc(F[x][y], F[x-1][y]), inc(F[x][y], F[x][y-1]);

    jc[0] = 1;
    for (int i=1;i<=8000;i++) jc[i] = 1LL * jc[i-1] * i % mod;

    int ans = 0;
    for (int _=1;_<=n;_++) inc(ans, F[ c+a[_] ][ c+b[_] ]);
    for (int _=1;_<=n;_++) inc(ans, mod - C(2*a[_]+2*b[_], 2*a[_]) );
    ans = 1LL * ans * qp(2, mod-2) % mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 65792
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力

b = input().split(" ")
i=1
while 1:
  flag=0
  for item in b:
    if int(item)%2**i!=0:
      #print(item)
      flag=1
  if flag==1:
    break
  i=i+1

print(i-1)

Measured memory_bytes: 3060
n = int(input())
cnt = 0
flag = False
for _ in range(n):
    c, d = map(int, input().split())
    if c == d:
        cnt += 1
    else:
        if cnt >= 3:
            flag = True
        cnt = 0
if cnt >= 3:
    flag = True
print('Yes' if flag else 'No')


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

int main() {
  int a, b, c, n=0;
  cin >> a >> b >> c;
  
  if(a==b)
    n++;
  if(b==c)
    n++;
  if(c==a)
    n++;
  
  if(n==1)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
input()
tmp = list(map(int, input().split(" ")))
T = tmp[0]
A = tmp[1]
H = list(map(int, input().split(" ")))

ans_diff = 999999
ans = -1

for i in range(len(H)):
    if abs(A - (T - (H[i] * 0.006))) < ans_diff:
        ans_diff = abs(A - (T - (H[i] * 0.006)))
        ans = i + 1

print(ans)

Measured memory_bytes: 3064
import scala.io.StdIn.readLine

object Main extends App {

  val ins: List[Int] = readLine.toList.map(_.toString.toInt)

  val nums = ins.sliding(3).map { ns =>
    100 * ns(0) + 10 * ns(1) + ns(2)
  }.toList

  val nearest = nums.map(n => math.abs(753 - n)).sorted.head

  println(nearest)

}

Measured memory_bytes: 25428
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Sparsh Sanchorawala
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DAtCoDeerAndRockPaper solver = new DAtCoDeerAndRockPaper();
        solver.solve(1, in, out);
        out.close();
    }

    static class DAtCoDeerAndRockPaper {
        public void solve(int testNumber, InputReader s, PrintWriter w) {
            char[] a = s.next().toCharArray();
            int res = 0;
            for (int i = 0; i < a.length; i++) {
                if (a[i] == 'p')
                    res--;
                res += i % 2;
            }
            w.println(res);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return nextString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 33392
#include <iostream>

using namespace std;

int main() {
    int K, S;
    cin >> K >> S;

    int ans = 0;
    for (int x = 0; x <= K; ++x) {
        for (int y = 0; y <= K; ++y) {
            int z = S - x - y;
            if (0 <= z && z <= K) ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3168
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int cost;
	if(a>=13)cost=b;
	else if(a>=6)cost=b/2;
	else cost=0;
	cout<<cost;
	return 0;
 } 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vll vector<ll>

using namespace std;

const ll N = 3e5+100;
const ll MOD = 1e9+7;

int main()
{


	ll n,a,b;
	cin >> n >>a >>b;

	cout << min(n*a,b)  << endl;
		
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
constexpr auto INF = 2147483647;
static const double EPS = pow(10,-10);
typedef long long ll;
static int COUNTER_CLOCKWISE = 1;
static int CLOCKWISE = -1;
static int ONLINE_BACK = 2;
static int ONLINE_FRONT = -2;
static int ON_SEGMENT = 0;




class Vector2{
  public:
  double x, y;
  Vector2(){}
  Vector2(double x, double y): x(x), y(y) {}

  Vector2 operator + (Vector2 v) {
    return Vector2(x + v.x , y + v.y);
  }
  Vector2 operator - (Vector2 v) {
    return Vector2(x - v.x , y - v.y);
  }

  Vector2 operator * (double d){
    return Vector2(d*x, d*y);
  }

  double norm(){
    return pow(x,2) + pow(y,2);
  }

};

double dot(Vector2 a, Vector2 b){
  return a.x * b.x + a.y * b.y; 
}

double cross(Vector2 a, Vector2 b){
  return a.x * b.y - a.y*b.x;
}

Vector2 projection(Vector2 a, Vector2 b, Vector2 p){
  Vector2 base = b - a;
  Vector2 hypo = p - a;
  double norm_base = pow(base.x,2) + pow(base.y,2);

  Vector2 x;
  x = a + base*(dot(hypo,base) / norm_base);
  return x;
}

Vector2 refrection(Vector2 a, Vector2 b, Vector2 p){
  Vector2 v, p_projection;
  p_projection = projection(a,b,p); 
  v = p_projection + (p_projection - p);
  return v;
}

int ccw(Vector2 a, Vector2 b, Vector2 p){
  Vector2 hypo = p - a;
  Vector2 base = b - a;
  if(cross(base,hypo) > EPS) return COUNTER_CLOCKWISE;
  if(cross(base,hypo) < -EPS) return CLOCKWISE;
  if(dot(base,hypo) < -EPS) return ONLINE_BACK;
  if(hypo.norm() > base.norm()) return ONLINE_FRONT;
  return ON_SEGMENT;
}

bool intersect(Vector2 a,Vector2 b,Vector2 p,Vector2 q){
  int t1, t2;
  t1 =ccw(a,b,p)*ccw(a,b,q);
  t2 =ccw(p,q,a)*ccw(p,q,b);
  if(t1 <= 0 && t2 <= 0) return true;
  else return false;
}




int main(){
  Vector2 a,b,p,q;
  int queri;
  cin >> queri;
  rep(i,queri){
    cin >> a.x >> a.y >> b.x >> b.y;
    cin >> p.x >> p.y >> q.x >> q.y;
    if(intersect(a,b,p,q)) cout <<  1;
    else cout << 0;
    cout << endl;
  }
  return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}

#define CD complex<double>
#define PDD pair<double, double> 
using namespace std;

const int max_n = 6e5+10;




int main() {
	make(n);
	makev(v, n);
	bool byl = false;
	int ans = 0;
	FOR(i,0,n) {
		if (byl && v[i] == v[i-1]) {
			ans++;
			byl = false;
		} else {
			byl = true;
		}
	}
	printf("%d\n", ans);
}





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

int main(){
    int h,w; cin >> h >> w;
    int x,y;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            string s; cin >> s;
            if(s == "snuke"){
                x = i+1; y = j;
            }
        }
    }
    cout << char(y+'A') << x << endl;
    return 0;
}

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

typedef long long ll;

ll powmod(ll x, ll y = P - 2, ll p = P) {
	ll ans = 1;
  	while(y) {
		if(y & 1) ans = ans * x % p;
    	x = x * x % p;
      	y >>= 1;
    }
  	return ans;
}

ll Fac[200010], Rev[200010];

int main() {
	int n, a, b, c;
  	scanf("%d%d%d%d", &n, &a, &b, &c);
  	if(c == 100) {puts("RuYaSuiHe"); assert(0);}
  a = a * powmod(100) % P, b = b * powmod(100) % P, c = c * powmod(100) % P;
	int s = a + b;
	a = a * powmod(s) % P, b = b * powmod(s) % P;
  	for(int i = 0; i <= 2 * n; i++) Fac[i] = !i ? 1 : Fac[i - 1] * i % P;
  	Rev[2 * n] = powmod(Fac[2 * n]);
  for(int i = 2 * n; i >= 1; i--) Rev[i - 1] = Rev[i] * i % P;
  ll ans = 0;
  	for(int i = 0; i < n; i++) {
      	ans = (ans + Fac[n + i - 1] * Rev[i] % P * Rev[n - 1] % P * powmod(a, n) % P * powmod(b, i) % P * (n + i)) % P;
    	ans = (ans + Fac[n + i - 1] * Rev[i] % P * Rev[n - 1] % P * powmod(b, n) % P * powmod(a, i) % P * (n + i)) % P;
    }
  printf("%lld\n", (ans * powmod(1 - c) % P + P) % P);
	return 0;
}

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

int main(){
    int h,w,n;
    cin >> h >> w >> n;
    int a=max(h,w);
    int ans;
    if(n%a>0){
        ans=n/a+1;
    }else{
        ans=n/a;
    }
    cout << ans << endl;

}

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

h = list(map(int,input().split()))

c = 0

m = max(h)
for i in range(1,m+1)[::-1]:
    l = -2
    for j in range(n):
        if(h[j] == i):
            if(j != l+1):c += 1
            h[j] -= 1
            l = j
print(c)

Measured memory_bytes: 3060
package main

import (
    "fmt"
)

func main() {
    var x, y int
    fmt.Scan(&x, &y)
    if x % y == 0 {
        fmt.Println(-1)
    } else {
        i := 1
        for {
            if x * i % y != 0 {
                fmt.Println(x * i)
                break
            }
                i++
        }
    }
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int main(){
  int a,b,k;
  cin>>a>>b>>k;
  fr(i,k){
    if(i%2){b/=2;a+=b;}
    else{a/=2;b+=a;}
  }
  cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <string.h>
#include <set>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

typedef double LD;
typedef long long LL;
typedef pair<int, int> PII;
#define MP make_pair
#define PB push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, t) FOR(i,0,t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())

const LL MOD = 1000000007;
const int INF = 1e9;
const LL LINF = 1LL * INF * INF;
const int MAXN = 2007;
const LD EPS = 1e-7;

int n, A[MAXN];
bool used[MAXN];
vector <int> B[MAXN];
bool G[MAXN][MAXN];

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

void dfs(int v)
{
	vector <int> C, P;
	used[v] = true;
	REP(i, n)
	{
		if (G[v][i] && !used[i])
		{
			C.push_back(i);
			dfs(i);
		}
	}
	P.resize(SZ(C));
	B[v].push_back(A[v]);
	while (true)
	{
		int mx = 0, c;
		REP(i, SZ(C))
		{
			if (P[i] < SZ(B[C[i]]) && B[C[i]][P[i]] > mx)
			{
				mx = B[C[i]][P[i]];
				c = i;
			}
		}
		if (mx == 0) break;
		B[v].push_back(mx);
		++P[c];
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("In.txt", "r", stdin);
	cin >> n;
	REP(i, n) cin >> A[i];
	sort(A, A + n);
	REP(i, n)
	{
		REP(j, i)
			if (gcd(A[i], A[j]) > 1)
				G[i][j] = G[j][i] = true;
		G[i][n] = G[n][i] = true;
	}
	dfs(n);
	FOR(i, 1, n + 1)
		cout << B[n][i] << ' ';
	//cout << endl; system("pause");
	return 0;
}

Measured memory_bytes: 15104
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

int n;
vector<int>edge[5005];

bool rem[250005];
int sub[250005];
int make(int v,int u){
	int cnt=1;
	for(int i=0;i<edge[v].size();i++){
		int v2=edge[v][i];
		if(rem[v2] || v2==u) continue;
		cnt+=make(v2,v);
	}
	return sub[v]=cnt;
}
P search(int v,int u,int siz){
	//size and index
	P res=mp(INF,-1);
	int s=1,m=0;
	for(int i=0;i<edge[v].size();i++){
		int v2=edge[v][i];
		if(rem[v2] || v2==u) continue;
		res=min(res,search(v2,v,siz));
		m=max(m,sub[v2]);
		s+=sub[v2];
	}
	m=max(m,siz-s);
	res=min(res,mp(m,v));
	return res;
}

ll dp[2][5005];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[5005],R[5005];
void make(){
	F[0] = 1;
	for(int i=1;i<5005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<5005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}
int main(){
	cin >> n;
	make();
	rep(i,n-1){
		int a,b; cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	make(1,-1);
	int cent=search(1,-1,sub[1]).sc;
	make(cent,-1);
	vector<int>vec;
	rep(i,edge[cent].size()){
	    int to = edge[cent][i];
	    vec.pb(sub[to]);
	}
	dp[0][0] = 1;
	int cur = 0, nxt = 1;
	rep(i,vec.size()){
		rep(j,5005) dp[nxt][j] = 0;
		rep(j,5005){
			if(dp[cur][j] == 0) continue;
			rep(k,vec[i]+1){
				ll w = dp[cur][j] * modpow(C(vec[i],k),2) % mod * F[k] % mod;
				dp[nxt][j+k] += w;
			}
		}
		swap(cur,nxt);
		rep(j,5005) if(dp[cur][j] >= mod) dp[cur][j] %= mod;
	}
	ll ans = 0;
	rep(j,5005){
		if(dp[cur][j] == 0) continue;
		if(j%2 == 0) ans += dp[cur][j] * F[n-j] % mod;
		else ans -= dp[cur][j] * F[n-j] % mod;
	}
	cout << (ans%mod+mod)%mod << endl;
}

Measured memory_bytes: 1152
label = {}
flow = {}
s, t = 'S', 'T'

def printpath(path):
    return
    for u, v in zip(path, path[1:]):
        print("%s -%d-> " % (label[u], flow[(u,v)]), end="")
    print("")

def printflow():
    return
    print("--flow--")
    for r in R:
        for b in edges[r]:
            print("  ", label[r], label[b], "s->r=%d"%flow[(s, r)], ", r->b=%d"%flow[(r, b)], ", b->t=%d"%flow[(b, t)])
            #print("  ", label[r], label[b], "r->s=%d"%flow[(r, s)], ", b->r=%d"%flow[(b, r)], ", t->b=%d"%flow[(t, b)])
        if edges[r]:
            print()

def findpath(v, t, edges, flow, visited):
    visited.add(v)
    #print(label[v], edges[v])
    for u in edges[v]:
        if u in visited:
            continue
        if flow[(v, u)] == 1:
            continue
        if u == t:
            return [v, t]
        path = findpath(u, t, edges, flow, visited)
        if path:
            return [v] + path
    return None

def max_match(R, B, edges):

    # init edge b - t
    for b in B:
        flow[(b, t)] = 0
        flow[(t, b)] = 1
        edges[b].append(t)

    edges[s] = []
    # init edge s - r
    for r in R:
        flow[(s, r)] = 0
        flow[(r, s)] = 1
        edges[s].append(r)

        # init flow r - b
        for b in edges[r]:
            flow[(r, b)] = 0
            flow[(b, r)] = 1

    change = True
    while change:
        printflow()
        change = False
        for r in R:
            if flow[(s, r)] == 1:
                continue
            path = findpath(r, t, edges, flow, set([s]))
            if not path:
                continue
            #printpath(path)
            path = [s] + path
            for u, v in zip(path, path[1:]):
                flow[(u, v)] = 1
                flow[(v, u)] = 0
            #change = True
    printflow()
    return flow

def solve(R, B, edges):
    flow = max_match(R, B, edges)

    match = 0
    for r in R:
        for b in edges[r]:
            match += flow[(r, b)]
    return match
            

N = int(input())

R = [tuple([int(x) for x in input().split()]) for _ in range(N)]
B = [tuple([int(x) for x in input().split()]) for _ in range(N)]
for i, r in enumerate(R):
    label[r] = "R%d" % (i+1)
    #print(label[r], r)
for i, r in enumerate(B):
    label[r] = "B%d" % (i+1)
    #print(label[r], r)
label[s] = 'S'
label[t] = 'T'

edges = {}
for r in R:
    edges[r] = []
for b in B:
    edges[b] = []

for r in R:
    rx, ry = r
    for b in B:
        bx, by = b
        if rx < bx and ry < by:
            edges[r].append(b)
            edges[b].append(r)


print(solve(R, B, edges))




Measured memory_bytes: 4112
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
	
	int n;
	
	while(cin >> n, n) {
		bool f = false;
		vector<int> IDs;
		unordered_map<int, long long> result;
		
		for(int i = 0; i < n; ++i) {
			int ID;
			long long price, number;
			cin >> ID >> price >> number;
			
			IDs.push_back(ID);
			result[ID] += price * number;
		}
		
		unordered_set<int> used;
		
		for(int ID : IDs) {
			if(used.count(ID)) continue;
			
			if(result[ID] >= 1000000) {
				cout << ID << endl;
				f = true;
			}
			used.insert(ID);
		}
		
		if(!f) {
			cout << "NA" << endl;
		}
		
	}
	
	return 0;
}

Measured memory_bytes: 1332
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

static const int M = 31623;

int main()
{
  vector<int> primes;
  primes.push_back(2);
  for (int i = 3; i <= M; i += 2) {
    bool f = true;
    int r = (int)sqrt(i);
    for (int j = 0; primes[j] <= r; ++j) {
      if (i % primes[j] == 0) {
        f = false;
        break;
      }
    }
    if (f) {
      primes.push_back(i);
    }
  }

  int N;
  while (scanf("%d", &N), N) {
    int rest = N;
    long long sum = 1;
    for (int i = 0; i < (int)primes.size(); ++i) {
      int p = primes[i];
      if (rest % p == 0) {
        long long term = 1;
        long long powp = p;
        while (rest % p == 0) {
          rest /= p;
          term += powp;
          powp *= p;
          if (term > 2*N) goto abundant;
        }
        sum *= term;
        if (sum > 2*N) goto abundant;
      }
    }
    if (rest > 1) {
      sum *= 1 + rest;
    }
    sum -= N;
    if (N == sum) {
      puts("perfect number");
    } else if (N < sum) {
abundant:
      puts("abundant number");
    } else {
      puts("deficient number");
    }
  }
}

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


using namespace std;

typedef long long ll;
#define SWAP(x,y,z) {if ( y > z ) swap(y,z); if ( x > y ) swap(x,y); if (y > z) swap(y,z);}

double const eps = 1e-10;

int a[100100];


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

    int n;
    cin >> n;
    cout << n*800 - (n/15*200);


    return 0;

    // 274751WM
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner scan = new Scanner(System.in);
        String str1 = scan.nextLine();
        String str2 = scan.nextLine();
        scan.close();
        String[] str = str1.split(" ");
        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);

        StringBuffer answer = new StringBuffer();
        for (int i = 0; i < a; i++) {
            if (i == b-1){
                String temp = String.valueOf(str2.charAt(i));
                answer.append(temp.toLowerCase());
            } else {
                answer.append(str2.charAt(i));

            }
        }
        System.out.println(answer);

        }

    }


Measured memory_bytes: 22228
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using static MyIO;


public class A
{
	public static void Main()
	{
		int A = GetInt();
		char op = GetString()[0];
		int B = GetInt();
		Console.WriteLine((op == '+') ? A + B : A - B);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

Measured memory_bytes: 11092
# -*- coding: utf-8 -*-
import heapq
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(Q):
    sb = 0

    l = []
    r = []
    sl = 0
    sr = 0

    for q in Q:
        if q[0] == 1:
            _, a, b = q
            heapq.heappush(l, -a)
            sl += a

            if len(l) > len(r) + 1:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a

            while l and r and -l[0] > r[0]:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a

                a = heapq.heappop(r)
                heapq.heappush(l, -a)
                sl += a
                sr -= a

            sb += b
        else:
            x = -l[0]
            print(x, abs(sl - len(l)*x) + abs(sr - len(r)*x) + sb)

def main():
    N = read_int()
    Q = [read_int_n() for _ in range(N)]
    slv(Q)


if __name__ == '__main__':
    main()


Measured memory_bytes: 111580
// Code By H~S~C
#ifdef ONLINE_JUDGE
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize("Os")
#pragma GCC optimize("Og")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,sse,sse2,sse3,ssse3,sse4")
#endif
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define pb push_back
#define rep(i,n) for (int i=0;i<(n);++i)
#define rep1(i,n) for (int i=1;i<=(n);++i)
#define Rep(i,a,b) for (int i=(a);i<=(b);++i)
#define All(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define sqr(s) ((s)*(s))
#define MP make_pair
#define fillset(a,val) memset(a,val,sizeof(a))
#define X first
#define Y second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int,int> pii;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double EPS=1e-9,PI=acos(-1.0);
const int mod1=1000000007,mod2=998244353;
//....................密..........封..........线..........下..........禁..........止..........hack...............................................
const int Maxn=200005;
ll n,d,a[Maxn],dpl[Maxn],dpr[Maxn],ans;
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>d;rep(i,n) cin>>a[i],ans+=a[i];
	ans+=(n-1)*d;dpl[0]=a[0];dpr[n-1]=a[n-1];
	rep1(i,n-1) dpl[i]=min(a[i],dpl[i-1]+d);
	for (int i=n-2;~i;--i) dpr[i]=min(a[i],dpr[i+1]+d);
	rep1(i,n-2) ans+=min(dpl[i],dpr[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
ll inf = 1e10;

ll gcd(ll a, ll b){
  return (b != 0) ? gcd(b, a%b) : a;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<string> m, a, r, c, h;
  rep(i, n){
    string tmp;
    cin >> tmp;
    if(tmp[0] == 'M')      m.push_back(tmp);
    else if(tmp[0] == 'A') a.push_back(tmp);
    else if(tmp[0] == 'R') r.push_back(tmp);
    else if(tmp[0] == 'C') c.push_back(tmp);
    else if(tmp[0] == 'H') h.push_back(tmp);
  }
  ll ans = 0;
  vector<ll> num(5);
  num[0] = m.size();
  num[1] = a.size();
  num[2] = r.size();
  num[3] = c.size();
  num[4] = h.size();
  for(int i = 0; i < 3; ++i){
    for(int j = i+1; j < 4; ++j){
      for(int k = j+1; k < 5; ++k) ans += num[i]*num[j]*num[k];
    }
  }
    
    
  cout << ans << "\n";
  
}  

Measured memory_bytes: 5748
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define iter(it,c) for(auto it=c.begin(); it!=c.end(); ++it)
#define rep(i,b) for(int i=0; i<int(b); i++)
typedef int Weight;
int const inf = 1e8;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
        src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void dijk(Graph const&g, int s, vector<Weight> &dist, vi &prev) {
    int n = g.size();
    dist.assign(n, inf); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> q; // "e < f" <=> "e.weight > f.weight"
    q.push(Edge(-2, s, 0));
    while(q.size()) {
        Edge e = q.top();
        q.pop();
        if (prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        iter(f,g[e.dst]) {
            if (dist[f->dst] > e.weight+f->weight) {
                dist[f->dst] = e.weight+f->weight;
                q.push(Edge(f->src, f->dst, e.weight+f->weight));
            }
        }
    }
}

int main(){
    int n,k;
    while(cin>>n>>k, n|k){
        Graph g(n);
        rep(i,n) g[i].reserve(n-1);
        rep(i,k){
            int op; cin>>op;
            if(op==1){
                int a,b,c; cin>>a>>b>>c;
                a--; b--;
                g[a].push_back(Edge(a,b,c));
                g[b].push_back(Edge(b,a,c));
            } else {
                int a,b; cin>>a>>b;
                a--; b--;
                vi d,p;
                dijk(g,a,d,p);
                if(d[b]==inf){
                    cout << -1 << endl;
                } else {
                    cout << d[b] << endl;
                }
            }
        }
    }
}

Measured memory_bytes: 1324
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
using namespace std;

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

int main() {
	int n, d, x;
	cin >> n;
	cin >> d >> x;
	vi a(n);
	rep(i, 0, n) {
		cin >> a[i];
	}
	int ans = 0;
	rep(i, 0, n) {
		ans += (d%a[i] == 0) ? d / a[i] : d / a[i] + 1;
	}
	ans += x;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    vector<int> x(n, 0);
    for (int i = 1; i < n; i++) {
        for (int j = i; j < n; j += i) {
            x[j]++;
        }
    }

    ll r = 0;
    for (int c = 1; c < n; c++) {
        r += x[c];
    }

    cout << r << endl;

    return 0;
}

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

int main() {
  
  int N, K; cin >> N >> K; int count = 1, sum = 1, ans = 0;
  
  vector<int> vec(N), numberMemo(0);
  
  for (int i = 0; i < N; i++) cin >> vec[i];
  
  sort(vec.begin(), vec.end());
  
  for (int i = 0; i < N - 1; i++) {
    
    if (vec[i] == vec[i + 1]) {
      count++;
    }
    
    else {
      numberMemo.push_back(count);
      count = 1; sum++;
    }
    
    if (i == N - 2) numberMemo.push_back(count);
    
  }
  
  if (sum <= K) { cout << 0 << endl; return 0; }
  
  sort(numberMemo.begin(), numberMemo.end());
  
  for (int i = 0; i < sum - K; i++) ans += numberMemo[i];
  
  cout << ans << endl;
  
}

Measured memory_bytes: 5012
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    double p = 0.0;
    int pi = 0;

    for(int i=1; i<50001; i++){
      p = i * 1.08;
      pi = (int) p;
      if (pi == n){
        System.out.println(i);
        return;
      }
    }
    
    System.out.println(":(");
    
  }
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define forn(i,a,b) for(int i=a;i<b;i++)
#define ft first
#define sd second
#define sz size()
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
//cout << fixed << setprecision(12) <<x<<endl;

int main(){
fastIO;
#ifdef LOCAL
     freopen("in.txt", "r", stdin);
#endif
int n,k;
cin>>n>>k;
string s;
cin>>s;
//cout<<s[k]<<endl;
s[k-1]=tolower(s[k-1]);
cout<<s<<endl;

}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define endl "\n"
#define int long  long 

using namespace std ; 


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; 
                                                                                                                 
	int x ; 
	cin >> x ; 
	if(x >= 30)
		cout << "Yes"  ; 
	else 	
		cout <<"No" << endl ;	                                                                        
}


Measured memory_bytes: 3636