akhauriyash/Code-Regression huggingface dataset:
//Written by Zhu Zeqi
//Come on,baby
//Hack,please
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define CLR(x) memset(x,0,sizeof x)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define MAX 1000000000000000000
#define MOD 1000000007
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f
typedef long long ll;
//orz yht
using namespace std;
string i_s(int x){
	if(x==0)
	return "0";
	string ret="";
	while(x){
		ret=ret+(char)(x%10+'0');
		x/=10;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}
string add(string a,string b){
	if(a=="")
	a="0";
	if(b=="")
	b="0";
	if(a.length()<b.length())
	swap(a,b);
	while(b.length()<a.length()){
		b='0'+b;
	}
	for(int i=0;i<a.length();i++){
		a[i]=a[i]+(b[i]-'0');
	}
	bool big=false;
	for(int i=a.length()-1;i>=0;i--){
		if(big){
			a[i]++;
		}
		big=false;
		if(a[i]>'9'){
			a[i]=a[i]-10;
			big=true;
		}
	}
	if(big)
	a='1'+a;
	return a;
}
string mul(string a,string b){
	vector<int> va,vb;
	if(a=="0" || b=="0")
	return "0";
	string ans;
	for(int i=0;i<a.length();i++){
		va.push_back(a[i]-'0');
	}
	for(int i=0;i<b.length();i++){
		vb.push_back(b[i]-'0');
	}
	reverse(va.begin(),va.end());
	reverse(vb.begin(),vb.end());
	vector<int> res;
	res.clear();
	res.resize(1005);
	for(int i=0;i<a.length();i++){
		for(int j=0;j<b.length();j++){
			res[i+j]+=(va[i]*vb[j]);
		}
	}
	for(int i=0;i<1005;i++){
		if(res[i]>9){
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	for(int i=0;i<1005;i++){
		ans+=(res[i]+'0');
	}
	reverse(ans.begin(),ans.end());
	int k=0;
	while(ans[k]=='0'){
		k++;
	}
	ans=ans.substr(k);
	return ans;
}
bool is_prime(int n){
	if(n<2)
    return false;
    for(int i=2;i*i<=n;i++)
    if(n%i==0)
    return false;
    return true;
}
int main(){
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	int n,ans=0;
    cin>>n;
    int a[1005],b[1005],c[1005];
    for(int i=0;i<n;i++){
        cin>>a[i];
        cin>>b[i];
        ans+=b[i]-a[i];
    }
    cout<<ans+n;
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>


int main(void)
{
    int a;
    scanf("%d",&a);
    if(a%10==1)a+=8;
    else a-=8;
    if((a/10%10)==1)a+=80;
    else a-=80;
    if((a/100)==1)a+=800;
    else a-=800;
    printf("%d\n",a);

    return 0;
}


Measured memory_bytes: 128
def input():
    s = raw_input()
    return int(s)

def calc_min(sec):
    s = sec
    min = s / 60
    cal = min

    if min >= 59:
        houre = min / 60
        houre = int(houre) * 60
        min = min - houre

    return [min, cal]

def calc_hour(min):
    m = min
    houre = m / 60

    return int(houre)

def calc_sec(min, input_time):
    m = min
    t = input_time
    sec = t - (m * 60)
    return sec

while True:
    ss = input()

    if ss >= 0 and ss < 86400:
        break

c_min = calc_min(ss)[0]
c_houre = calc_hour(calc_min(ss)[1])
c_sec = calc_sec(calc_min(ss)[1], ss)

print(str(c_houre) + ":" + str(c_min) + ":" + str(c_sec))

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

int main(){
  int n;
  cin>>n;
  vector<int> v(n);
  int index=0;
  for(int i=0;i<n;i++){
    cin>> v[i];
    if(v[i]>v[index]){index=i;}
  }
  int max = v[index];
  v.erase(v.begin()+index);
  int r=0,k=-1;
  for(int i=0;i<n;i++){
    int temp = min(v[i],max-v[i]);
    if(temp>k){ r=i; k=temp;}
  }
  cout<<max<<" "<<v[r]<<"\n";

}


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

namespace P0022_MaximumSumSequence
{
    class Program
    {

        static void Main(string[] args)
        {
            int cntLine;

            List<List<int>> lines = new List<List<int>>();

            do
            {
                cntLine = int.Parse( Console.ReadLine());
                
                List<int> line = new List<int>();

                for (int i = 1; i <= cntLine; i++) 
                {
                    line.Add(int.Parse(Console.ReadLine()));
                }

                lines.Add(line);

            }
            while (cntLine != 0);
            

            foreach (List<int> line in lines)
            {

                if (line.Count == 0) 
                {
                    break;
                }

                List<int> newline = new List<int>();

                int sum1 = 0;

                int? ib = null;

                foreach (int i in line)
                {

                    if ((ib >= 0 && i < 0) || (ib < 0 && i >= 0))
                    {
                        newline.Add(sum1);
                        sum1 = i;
                    }
                    else
                    {
                        if (i < 0)
                        {
                            if (sum1 != 0)
                            {
                                newline.Add(sum1);
                            }
                            sum1 = i;
                        }
                        else
                        {
                            sum1 += i;
                        }

                    }

                    ib = i;
                }
                newline.Add(sum1);

                int Max = -100000;

                int lineLength = newline.Count;

                for (int i = 0; i < lineLength; i++) 
                {
                    int sum = 0;

                    for (int j = i; j < lineLength; j++)
                    {
                        sum += newline[j];

                        if (sum >= Max) 
                        {
                            Max = sum;
                        }
                    }

                }

                Console.WriteLine(Max);

            }

        }


    }

}

Measured memory_bytes: 5904
#include<iostream>
#include<cstdio>
#define min(a,b) (a<b?a:b)
long long n,x,a[4055],dp[4055][4055];
int main(){
    scanf("%lld%lld",&n,&x);
    for(int i=0;i<=2*n+10;i++)
        for(int j=0;j<=2*n+10;j++)
            dp[i][j]=1e15;
    for(int i=1;i<=n;i++){
       scanf("%lld",&a[i]);
       a[i+n]=a[i];
       dp[i][0]=a[i];
       dp[i+n][0]=a[i+n];
    }
    long long mini=1e15,ls;
    for(int i=n+1;i<=2*n;i++)
        for(int j=1;j<n;j++)
            dp[i][j]=min(dp[i][j-1],a[i-j]);
    for(int k=0;k<n;k++){
        ls=k*x;
        for(int i=n+1;i<=2*n;i++) ls+=dp[i][k];
        mini=min(ls,mini);
    }
    printf("%lld\n",mini);
    return 0;
}

Measured memory_bytes: 127360
use std::str::FromStr;
use std::fmt::Debug;

fn read_line<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()
}

fn main() {
    let vec: Vec<i32> = read_line();
    let (a, b, c) = (vec[0], vec[1], vec[2]);
    let minus = a - b;
    let ans = if c - minus < 0 { 0 } else { c - minus };
    println!("{}", ans);
}

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

int main(){

    int n;
    cin >> n;

    int ma=0;
    vector<int> h(n+1);
    h[0]=0;
    vector<int> t(n);

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

    for(int i=0;i<n;i++){
        t[i]=h[i+1]-h[i];
    }

    int ans=0,temp=0;

    for(int i=0;i<n;i++){
        if(t[i]>=0){
            temp+=t[i];
        }else{
            ans+=temp;
            temp=0;
        }
        if(i==n-1){
            ans+=temp;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int INF = numeric_limits<int>::max() / 2;
using ll = long long;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    cout << n * m - n - m + 1 << endl;
    return 0;
}


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

const int inf = 1e9;

pair<int,int> convert(string s){
    return { s[0]-'a', atoi(&s[2])-1 };
}

int h,w;
int sign[20][20];
int sig[20][20][4];
int c[20][20][4];
int vis[20][20][4][101];

int main() {
    while(cin >> h >> w && h){
        const int dy[] = {-1, 0, 1, 0};
        const int dx[] = {0, -1, 0, 1};
        int d, ns;
        cin >> d >> ns;
        memset(sign, 0, sizeof(sign));
        memset(sig, 0, sizeof(sig));
        memset(c, 0, sizeof(c));
        memset(vis, 0, sizeof(vis));
        rep(i, ns){
            string s;
            int k;
            cin >> s >> k;
            int y,x;
            tie(y,x) = convert(s);
            sign[y][x] = k;
        }
        int nc;
        cin >> nc;
        rep(i,nc){
            string s1, s2;
            cin >> s1 >> s2;
            int x1, x2, y1, y2;
            tie(y1,x1) = convert(s1);
            tie(y2,x2) = convert(s2);
            rep(j,4){
                if(y1+dy[j] == y2 && x1+dx[j] == x2){
                    sig[y1][x1][j] = true;
                    sig[y2][x2][(j+2)%2] = true;
                    break;
                }
            }
        }

        int nj;
        cin >> nj;
        rep(i, nj){
            string s1, s2;
            int d;
            cin >> s1 >> s2 >> d;
            int x1, y1, x2, y2;
            tie(y1,x1) = convert(s1);
            tie(y2,x2) = convert(s2);
            rep(j,4){
                if(y1+dy[j] == y2 && x1+dx[j] == x2){
                    c[y1][x1][j] = d;
                    c[y2][x2][(j+2)%2] = d;
                    break;
                }
            }
        }

        string s, g;
        cin >> s >> g;
        int ys,xs,yg,xg;
        tie(ys,xs) = convert(s);
        tie(yg,xg) = convert(g);
        int ans = -1;
        using State = tuple<int,int,int,int>;
        priority_queue<State> q;
        q.emplace(0, ys, xs, 3);
        while(q.size()){
            int ct,cy,cx,cd;
            tie(ct,cy,cx,cd) = q.top(); q.pop();
            ct *= -1;
            if(vis[cy][cx][cd][ct]) continue;
            vis[cy][cx][cd][ct] = true;
            if(cy == yg && cx == xg){
                ans = ct;
                break;
            }
            rep(i,4){
                if(abs(cd-i) == 2 || sig[cy][cx][i]) continue;
                int ny = cy + dy[i];
                int nx = cx + dx[i];
                if(ny < 0 || h <= ny || nx < 0 || w <= nx) continue;
                int nt = ct + d + c[cy][cx][i];
                if(sign[ny][nx] == 0 || (((nt/sign[ny][nx])%2) ^ (i%2==0))){
                    q.emplace(-nt, ny, nx, i);
                }
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 3928
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    m = min(a[i], b[i])
    a[i] -= m
    b[i] -= m
    ans += m
    m = min(a[i + 1], b[i])
    a[i + 1] -= m
    b[i] -= m
    ans += m
print(ans)

Measured memory_bytes: 18624
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <deque>
#define inf 0x3F3F3F3F
using namespace std;
struct Node
{
	int x,c;
};
deque<Node>q;
unordered_map<int,vector<int> >e[100005];
unordered_map<int,int>d[100005];
vector<int>g[100005];
int main(void)
{
	int i,x,y,c,cost,n,m,ans=inf;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		e[x][c].push_back(y);
		e[y][c].push_back(x);
		g[x].push_back(c);
		g[y].push_back(c);
	}
	d[0][0]=0;q.push_back((Node){1,0});
	while(!q.empty())
	{
		x=q.front().x;c=q.front().c;cost=d[x][c];q.pop_front();
		if(d[x].find(0)==d[x].end()||d[x][0]>cost)
		{
			d[x][0]=cost;q.push_front((Node){x,0});
		}
		if(c==0)
		{
			for(i=0;i<g[x].size();++i)
			{
				y=g[x][i];
				if(d[x].find(y)==d[x].end()||d[x][y]>cost+1)
				{
					d[x][y]=cost+1;q.push_back((Node){x,y});
				}
			}
			continue;
		}
		for(i=0;i<e[x][c].size();++i)
		{
			y=e[x][c][i];
			if(d[y].find(c)==d[y].end()||d[y][c]>cost)
			{
				d[y][c]=cost;q.push_front((Node){y,c});
			}
		}
	}
	unordered_map<int,int>::iterator j;
	for(j=d[n].begin();j!=d[n].end();++j)ans=min(ans,j->second);
	if(ans!=inf)printf("%d\n",ans);
	else printf("-1\n");
	return 0;
}

Measured memory_bytes: 77824
alice, bob = gets.split(" ").map(&:to_i)
line = (2..13).to_a.push(1)
if line.index(alice) == line.index(bob)
  puts "Draw"
elsif line.index(alice) > line.index(bob)
  puts "Alice"
elsif line.index(alice) < line.index(bob)
  puts "Bob"
end

Measured memory_bytes: 3836
n = int(input())
l = list(map(int, input().split()))
if 0 in l:
    print(0)
else:
    a = 0
    flag = 1
    for i in range(n):
        if i == 0:
            a = l[i]
        else:
            a *= l[i]
            if a > 1000000000000000000:
                flag = 0
                print(-1)
                break
    if flag:
        print(a)

Measured memory_bytes: 21796
#include <iostream>
#include <queue>
#include <vector>

struct node
{
  int name;
  std::vector<node*> neighbors;
  int distance{-1};
};

void solve(std::vector<node>& nodes)
{
  std::queue<node*> queue;
  auto& root = nodes.front();
  root.distance = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.front();
    queue.pop();

    for (auto* n : target->neighbors) {
      if (n->distance >= 0) continue;
      n->distance = target->distance + 1;
      queue.push(n);
    }
  }
}

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

  std::vector<node> nodes(n);
  for (int i = 0; i < n; ++i) {
    int u, k;
    std::cin >> u >> k;
    auto& node = nodes.at(u - 1);
    node.name = u;
    node.neighbors.resize(k);
    for (auto& nb : node.neighbors) {
      int v;
      std::cin >> v;
      nb = &nodes.at(v - 1);
    }
  }

  solve(nodes);

  for (const auto& node : nodes) {
    std::cout << node.name << ' ' << node.distance << std::endl;
  }
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
main(){
  int n,a[2222],res=0;
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if(a[i]+a[j]>a[k])res++;
      }
    }
  }
  cout<<res;
}


Measured memory_bytes: 256
import math

N,A,B = list(map(int, input().split()))

total = 0
ans = []

# 文字列に変換
def findSumdigit(n):
    s = str(n)
    # 1文字ずつ数値化して配列に入れる
    array = list(map(int,s))
    return sum(array)

for i in range(A,N+1):
    total = findSumdigit(i)
    if total>= A and total <= B :
        ans.append(i)

print(sum(ans))


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> v(8,0);
    int count = 0;
    for(int i=0;i<n;i++) {
        int a;
        cin>>a;
        if(a>=1 && a<=399) v[0] = 1;
        else if(a>=400 && a<=799) v[1] = 1;
        else if(a>=800 && a<=1199) v[2] = 1;
        else if(a>=1200 && a<=1599) v[3] = 1;
        else if(a>=1600 && a<=1999) v[4] = 1;
        else if(a>=2000 && a<=2399) v[5] = 1;
        else if(a>=2400 && a<=2799) v[6] = 1;
        else if(a>=2800 && a<=3199) v[7] = 1;
        else count++;
    }
    int a;
    for(int i=0;i<8;i++) {
        if(v[i]==1) a++;
    }
    if(a==0) {
        cout<<"1 ";
    }
    else cout<<a<<" ";
    int b = a+count;
    cout<<b;
    return 0;
}


Measured memory_bytes: 256
from sys import stdin

n, m, k = map(int, stdin.readline().rstrip().split())

a = list(map(int, stdin.readline().rstrip().split()))
b = list(map(int, stdin.readline().rstrip().split()))

A,B = [0],[0]

for i in range(n):
    A.append(A[i]+a[i])

for i in range(m):
    B.append(B[i]+b[i])

ans = 0
j = m
for i in range(n + 1):
    if A[i] > k:
        break
    while A[i]  > k- B[j]:
        j -= 1
    ans = max(ans, i + j)

print(ans)

Measured memory_bytes: 48576
import itertools
A,B,C=map(int,input().split())
K=int(input())

l=list(range(K+1))

for c  in itertools.product(l, repeat=3):
    if sum(c) == K and A*2**c[0]<B*2**c[1] and B*2**c[1]<C*2**c[2]:
      print("Yes")
      exit(0)
print("No")


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

int main(){
    int n, i, j, k, d, t, ans = 0;
    cin >> n;
    int p[15] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}, c[n+1][15] = {}, s[15] = {};
    for(i=1; i<=n; i++){
        d = i;
        for(j=0; j<15; j++){
            while(d%p[j] == 0){
                c[i][j]++;
                d /= p[j];
            }
        }
    }
    for(j=0; j<15; j++){
        for(i=1; i<=n; i++){
            s[j] += c[i][j];
        }
    }
    t = 0;
    for(i=0; i<15; i++){
        for(j=0; j<15; j++){
            if(i == j) continue;
            for(k=0; k<15; k++){
                if(i == k || j == k) continue;
                if(s[i] > 3 && s[j] > 3 && s[k] > 1 && i != j){
                    t++;
                }
            }
        }
    }
    ans += t/2;
    for(i=0; i<15; i++){
        for(j=0; j<15; j++){
            if(i == j) continue;
            if(s[i] > 13 && s[j] > 3){
                ans++;
            }
            if(s[i] > 23 && s[j] > 1){
                ans++;
            }
        }
    }
    for(i=0; i<15; i++){
        if(s[i] > 73){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;

signed main(){
  int k,a,b;
  cin>>k>>a>>b;
  if(k<=a||a+1>=b){
    cout<<k+1<<endl;
    return 0;
  }
  int s=k-a+1;
  int ans=a;
  //cout<<s<<" "<<ans<<endl;
  if(s%2==1){
    ans++;
    s--;
  }
  ans+=(s/2)*(b-a);
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int main(){
   string S;
   cin>>S;
   bool check=false;
   REP(i,S.size()-1){
       if(S[i]=='A'&&S[i+1]=='C'){
          check=true;
       }
   }
   if(check){
      cout<<"Yes"<<endl;
   }else{
      cout<<"No"<<endl;
   }
	return(0);
}

Measured memory_bytes: 256
def edpcC(n, abcs):
    coidx = ((1, 2), (2, 0), (0, 1))
    dp = [abcs[0]]
    for i in range(1, n):
        prev_dp = dp[i-1]
        cur_vals = abcs[i]
        new_d = []
        for j in range(3):
            tmp = [cur_vals[j][1] + p[1] for p in (prev_dp[c] for c in coidx[j])]
            new_d.append((j, max(tmp)))
        dp.append(new_d)
    print(max(dp[-1], key=lambda x:x[1])[1])
    
n = int(input())
abcs = [list(enumerate(map(int, input().split(' ')))) for _ in range(n)]
edpcC(n, abcs)

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

using namespace std;

int N, X;
int minim = 10000;

int main()
{
  cin >> N >> X;
  vector<int> m(N);
  for (int i = 0; i < N; i++)
  {
    cin >> m[i];
    X -= m[i];
    minim = min(minim, m[i]);
  }
  int syo = X / minim;
  cout << N + syo << endl;
  return 0;
}

Measured memory_bytes: 256
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    maxheight=0
    total=0
    for i in range(n):
        if a[i]<maxheight:
            total+=maxheight-a[i]
        maxheight=max(a[i],maxheight)
    print(total)




if __name__ == "__main__":

    main()


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

typedef pair<int, pair<int, int> > p;

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

    int N, M;
    cin >> N >> M;

    vector<bool> c(N);

    vector<int> x(N);
    vector<vector<p> > a(N);

    for(int i = 0; i < M; i++) {
        int L, R, D;
        cin >> L >> R >> D;
        L--;
        R--;

        a[L].push_back(make_pair(D, make_pair(L, R)));
        a[R].push_back(make_pair(-D, make_pair(R, L)));
    }

    stack<p> s;

    for(int i = 0; i < N; i++) {
        if(c[i]) continue;
        x[i] = 0;
        c[i] = true;
        for(int j = 0; j < a[i].size(); j++) {
            s.push(a[i][j]);
        }
        while(!s.empty()) {
            p z = s.top();
            int L = z.second.first;
            int R = z.second.second;
            int D = z.first;

            //cerr << L << " " << R << " " << D << endl;

            s.pop();

            if(c[R]) {
                if(x[R] - x[L] != D) {
                    cout << "No" << endl;
                    return 0;
                }
            } else {
                x[R] = x[L] + D;
                c[R] = true;
                for(int j = 0; j < a[R].size(); j++) {
                    s.push(a[R][j]);
                }
            }
        }
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 13184
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

int main(){
  ll N,K=0,ca=0,cb=0,cx=0;
  string S[10007];
  cin >> N;
  rep(i,N){
    cin >> S[i];
    rep(j,S[i].size()-1){
      if(S[i].substr(j,2)=="AB"){
        K++;
      }
    }
    if(S[i][0]=='B' && S[i][S[i].size()-1]!='A'){
      cb++;
    }
    if(S[i][0]!='B' && S[i][S[i].size()-1]=='A'){
      ca++;
    }
    if(S[i][0]=='B' && S[i][S[i].size()-1]=='A'){
      cx++;
    }
  }
  ll X=min(ca+cx,cx+cb);
  cout << ((ca==0 && cb==0) ? max(0LL,X-1) : X  )+K << endl;
}

Measured memory_bytes: 768
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		
		boolean f = false;
		String ans = "";
		for(int i=0;i<s.length();i++){
			char c = s.charAt(i);
			if(!f && c=='A'){
				f = true;
			}else if(f && c=='Z'){
				f = false;
				ans += "AZ";
			}
		}
		
		if(ans.equals("")){
			ans = "-1";
		}
		System.out.println(ans);
	}
	
}

Measured memory_bytes: 26056
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace::std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    vector<bitset<101>>dp(k+1);
    rep(i,k+1)dp[i].set();
    rep(i,k+1){
        int mex=dp[i]._Find_first();
        for(int d:a){
            if(i+d<=k)dp[i+d][mex]=0;
        }
        if(i==k){
            if(mex)cout<<"First"<<endl;
            else cout<<"Second"<<endl;
        }
    }
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;
int a[6],b[6];
void rotation(char c){
    int aoki;
    if(c=='N'){
        aoki=a[0];
        a[0]=a[1];
        a[1]=a[5];
        a[5]=a[4];
        a[4]=aoki;
    }
    else if(c=='S'){
        aoki=a[0];
        a[0]=a[4];
        a[4]=a[5];
        a[5]=a[1];
        a[1]=aoki;
    }
    else if(c=='E'){
        aoki=a[0];
        a[0]=a[3];
        a[3]=a[5];
        a[5]=a[2];
        a[2]=aoki;
    }
    else if(c=='W'){
        aoki=a[0];
        a[0]=a[2];
        a[2]=a[5];
        a[5]=a[3];
        a[3]=aoki;
    }
    else if(c=='R'){
        aoki=a[1];
        a[1]=a[2];
        a[2]=a[4];
        a[4]=a[3];
        a[3]=aoki;
    }
}
int main(){
    for(int i=0;i<6;++i){
        cin>>a[i];
    }
    for(int i=0;i<6;++i){
        cin>>b[i];
    }
    for(int i=1;i<=6;++i){
        if(a[0]==b[0]&&a[5]==b[5]){
            for(int i=0;i<4;++i){
                if(a[1]==b[1]&&a[2]==b[2]&&a[3]==b[3]&&a[4]==b[4]){
                    cout<<"Yes"<<endl;
                    return 0;
                }
                else rotation('R');
            }
        }
        if(i==1) rotation('N');
        else if(i==2) rotation('W');
        else if(i==3) rotation('W');
        else if(i==4) rotation('W');
        else if(i==5) rotation('N');
    }
    cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 3124
/*COMPETITIVE PROGRAMMING C++ TEMPLATE */

#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>
#include <climits>
#include <iomanip>

#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << "\n"
#define MOD 998244353

const long double PI = 3.141592653589793236L;

typedef long long int ll;
typedef long double ld;

using namespace std;

void solve()
{
    string s, t;
    cin >> s >> t;

    int n = s.size();

    int count = 0;

    for(int i = 0; i < n; i++)
    {
        if(s[i] != t[i])
        {
            count++;
        }
    }

    cout << count << endl;

}

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

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



Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<int> T(N);
  int sum = 0;
  for(int i = 0; i < N; i++) {
    cin >> T.at(i);
    sum += T.at(i);
  }
  int M, p, x;
  cin >> M;
  for(int i = 0; i < M; i++) {
    cin >> p >> x;
    cout << sum + (x - T.at(p - 1)) << endl;;
  }
  return 0;
}


Measured memory_bytes: 256
/**

   Author : sea_26

**/


#pragma GCC optimize("03")
#include <bits/stdc++.h>

using namespace std;

const int M = 1000000007;
const double PI = acos(-1.0);

// const double pi = atan2(0, -1);
// const double PI = 4 * atan(1);
// const double pi = 2*cos(0.0);

typedef long long ll;
typedef long double ld;

const int iinf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ln(x) (int)x.size()

#define bp(n)  __builtin_popcount(n)
#define bclz(n) __builtin_clzll(n)
#define bctz(n) __builtin_ctzll(n)
#define bip(n) __builtin_parity(n)

#define vsort(v) sort(v.begin(),v.end())
#define rvsort(v) sort(v.begin(),v.end(),greater<int>())

#define rep(n) for(int i=0; i<n; i++)
#define rrep(n) for(int i=n-1; i>=0; i--)
#define lrep(p,q) for(int i=p; i<=q; i++)
#define prep(n) for(int i=1; i*i<=n; i++)
#define it(a, x)  for(auto &a : x)
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

priority_queue<int> pq;

#define fs   ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

template< typename T> inline T lcm(T a, T b){ return (a / gcd(a,b)) * b; }
template< typename T> inline T MAX(T a, T b){ return a ^ ((a ^ b) & -(a < b)); }
template< typename T> inline T MIN(T a, T b){ return b ^ ((a ^ b) & -(a < b)); }
template< typename T> void tpns(T n){ rrep(30){ if(n & (1 << i)) pq.push(1 << i); } }
template< typename T> void SWAP(T &a, T &b){ a = ((a) ^= (b)),  b = ((b) ^= (a)),  a = ((a) ^= (b)); }
template< typename T> inline T ABS(T a){ int x = a >> sizeof(int) * CHAR_BIT - 1; return (a + x) ^ x; }
template< typename T> inline T mod(T a, T b){ return a >= b ? a % b : a; }
template< typename T> inline T gcd(T a, T b){ while (b) b ^= a ^= b ^= a %= b; return a; }

ll gcdextd(ll a, ll b, ll& x, ll& y) {
    if (!a) { x = 0; y = 1; return b; }
    ll y1,d;
    d = gcdextd(b % a, a, y, y1);
    x = y1 - (b / a) * y;
    return d;
}


/*
double WT() {
	return double(clock()) / CLOCKS_PER_SEC;
}

void ReT(){

	cout << "\nTime = " << fixed << setprecision(3) << WT()  << " Sec"<< endl;

exit(0);
}

*/


int A,B,T;
int main(){

        fs;
        cin >> A >> B >> T;
        cout << T/A * B << endl;

     //   ReT();

}


Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  Bs = list(map(int, input().strip().split()))
  As = [Bs[0]]
  for i in range(1, len(Bs)):
    As.append(min(Bs[i], Bs[i-1]))
  As.append(Bs[-1])
  print(sum(As))
    

if __name__=='__main__':
  main()



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

using namespace std;

const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.14159265;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); ++i)
#define RFOR(i,n,r) for(ll i = (ll)(n-1); i >= r; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n,0)
#define ALL(x) x.begin(),x.end()
#define CALL(x) x.cbegin(),x.cend()
#define RALL(x) x.rbegin(),x.rend()
#define CRALL(x) x.crbegin(),x.crend()

#define cout cout << setprecision(12)

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using vp = vector<pair<ll, ll>>;
using vs = vector<string>;
using vc = vector<char>;
using lst = list<ll>;
using pq = priority_queue<ll>;

template < typename T >
inline void dbg(T a) { cout << a << ' '; }

ll n, m, k;
//double d;
string s;
char c;

/*--------------------template--------------------*/

int main() {
    cin >> n;
  	vi a(n), answ(n), cnt(n), sub(n);
	fill(ALL(cnt),0);
	REP(i,n){
      cin>>a[i];
      cnt[a[i]-1]++;
    }
	
  	REP(i,n){
    	//cnt[i] = count(ALL(a),i+1);
    	answ[i] = cnt[i]*(cnt[i]-1)/2;
    	sub[i] = (cnt[i]-1)*(cnt[i]-2)/2;
    	//dbg(cnt[i]);	dbg(answ[i]);
    }
	k = accumulate(ALL(answ),(ull)0);
    REP(i,n) {
    	cout << k - answ[a[i]-1] + sub[a[i]-1] << endl;
    }
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

main(){
    int n;cin>>n;
    set<string> s;
    string temp;
    for(int i=0;i<n;i++){
        cin>>temp;
        s.insert(temp);
    }
    cout<<s.size();
}

Measured memory_bytes: 19208
#include<iostream>
#include<vector>

using namespace std;

int main(){

    string S;
    cin>> S;

    int n=S.size();
    for(int i=0; i<n-1; i++){
        if(S[i+1]==S[i]){
            cout<< i+1<< " "<< i+1+1<< endl;
            return 0;
        }
    }
    for(int i=0; i<n-2; i++){
        if(S[i]==S[i+2]){
            cout<< i+1<< " "<< i+1+2<< endl;
            return 0;
        }
    }
    
    cout<< -1<< " "<< -1<< endl;
    
    return 0;
}


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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()

int main() {
	string s;
	cin >> s;
	int temp = (s.size() - 2) / 2;
	int cnt = 0;
	FOR(i, 0, temp) {
		if (s[i] != s[s.size() - 1 - i]) {
			cnt++;
		}
	}
	pv(cnt)
	return(0);
}

Measured memory_bytes: 256
def insertion_sort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = v
        print(*A)


n = int(input())
m = list(map(int, input().split()))
print(*m)
insertion_sort(m,n)


Measured memory_bytes: 5980
#include <iostream>
#include <cctype>
#include <stack>
#include <string>
#define OPERAND_MAX 100
#define OPERATOR_MAX 99
using namespace std;

int main() {
    // input
    std::stack<int> operands; // empty stack
    string s;
    int val;
    while (cin >> s) {
        if ( s[0] != '+' && s[0] != '-' && s[0] != '*' ) {
            operands.push( stoi(s) );
        } else {
            int r = operands.top();
            operands.pop();
            int l = operands.top();
            operands.pop();
            switch ( s[0] ) {
                case '+':
                    val = l + r;
                    break;
                case '-':
                    val = l - r;
                    break;
                case '*':
                    val = l * r;
                    break;
                default:
                    break;
            }
            operands.push(val);
        }
    }
    
    // output
    cout << val << endl;
}


Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int res=999999,cnt=0;
  string s,n;
  cin >> s;
  for(char c='a';c<='z';c++){
    if(s.find(c) == string::npos){
      continue;
    }
    cnt = 0;
    n = s;
    while(1){
      bool f = false;
      REP(i,n.size()){
        if(n[i] != c){
          break;
        }
        if(i == n.size()-1)
          f = true;
      }
      if(f)
        break;
      REP(i,n.size()-1){
        if(n[i+1] == c){
          n[i] = c;       
        }
      }
      cnt++;
      n.erase(n.size()-1,1);
      
      
    }
    res = min(cnt,res);
  }
  cout << res << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 256
var
	i,n,a,b:integer;
    kk:boolean;
begin
	readln(n);
    readln(a,b);
    kk:=false;
    for i:=a to b do if (i mod n)=0 then kk:=true;
    if kk then writeln('OK') else writeln('NG');
end.

Measured memory_bytes: 1320
#include <bits/stdc++.h>
using namespace std;
int main(){
   string a;
   cin >> a;
   int x = 1;
   int b = 0;
   int ans = 0;
   vector<int> v(2019,0);
   for(int i=0;i<a.size();i++){
       b += (a[a.size()-i-1]-'0')*x;
       v[b%2019]++;
       x *= 10;
       x %= 2019;
       b %= 2019;
   }
    for(int i=0;i<2019;i++){
        ans += (v[i]*(v[i]-1))/2;
    }
    ans += v[0];
    cout << ans << endl;
}

Measured memory_bytes: 3760
#include <iostream>
using namespace std;
int main(void){
    int N;
    cin >> N;
    long long int ans = 0;
    int A;
    int A_max = 0;
    int A_max2 = 0;
    int A_argmax;
    for (int i = 0; i < N; i++) {
        cin >> A;
        if (A > A_max) {
            A_max2 = A_max;
            A_max = A;
            A_argmax = i;
        }
        else if (A > A_max2)
            A_max2 = A;
    }
    
    for (int i = 0; i < N; i++) {
        if (i != A_argmax)
            cout << A_max << endl;
        else
            cout << A_max2 << endl;
    }
}

Measured memory_bytes: 1664
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    cnt = [0]*(10**6+1)
    for a in A:
        if cnt[a]==0:
            x = 2*a   
            while x <= 10**6:
                cnt[x] += 1    
                x += a
        cnt[a] += 1
    print(len([1 for a in A if cnt[a]==1]))

if __name__ == '__main__':
    main()


Measured memory_bytes: 33760
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define DEBUG
#ifdef DEBUG
    #define IFD(...) __VA_ARGS__
    #define IFN(...)
    #define L cout<<__LINE__<<"\n";
    #define PRINT(...) __VA_ARGS__ cout<<__LINE__<" : "<<#__VA_ARGS__<<"\n"
    #define PRT(x) cout<<__LINE__<<" : "<<#x<<" = "<<x<<"\n"
#else // DEBUG
    #define IFD(...)
    #define IFN(...) __VA_ARGS__
    #define L
    #define PRINT(...) __VA_ARGS__
    #define PRT(x)
#endif // DEBUG

#define it iterator
#define rit reverse_iterator
#define mp make_pair
#define mems(a,b) memset(a,b,sizeof(a))
#define mem0(a) mems(a,0)
#define mem1(a) mems(a,1)
#define mem255(a) mems(a,255)
#define halt exit(0)
#define all(c) (c).begin() , (c).end()
#define sz(c) ((long long)((c).size()))
#define phb push_back
#define ppb pop_back
#define phf push_front
#define ppf pop_front
#define fort0(i,a,b) for(ll i=a,i##_TO=b;i<i##_TO;i++)
#define for0(i,n) fort0(i,0,n)
#define fort1(i,a,b) for(ll i=a,i##_TO=b;i<=i##_TO;i++)
#define for1(i,n) fort1(i,1,n)
#define ford(i,a,b) for(ll i=a,i##_TO=b;i>=i##_TO;i--)

using namespace __gnu_pbds;
using namespace std;

#define int ll

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template
<
    class key,
    class val=null_type,
    class comp=less<key>
>
using ord_set=tree
<
    key,
    val,
    comp,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,x;
    cin>>n>>x;
    int s=0,m=1e9;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        s+=t;
        m=min(m,t);
    }
    cout<<n+(x-s)/m;
}


Measured memory_bytes: 256
#ABC077C
def main():
    import sys, bisect
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    A.sort()
    B.sort()
    C.sort()
    #print(A, B, C)
    ans = 0
    #Bを起点
    for i in range(N):
        idxA = bisect.bisect_left(A, B[i])
        idxC = bisect.bisect_right(C, B[i])
        #print(idxA, idxC)
        ans +=idxA*(N-idxC)
    print(ans)

if __name__=='__main__':
    main()


Measured memory_bytes: 22720
// G++ MACro.cpp -std=c++14
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision; // cpp_int
 
#define P pair<int,int>
#define V vector<int>
#define M map<int,int>
#define S set<int>
#define L list<int>
 
#define pb(a) push_back(a)
#define mp make_pair
 
int main(){

  CIN(n,a,b);
  ll min_ = 1LL*a*(n-1)+b;
  ll max_ = 1LL*b*(n-1)+a;
  COUT(max(0LL,max_-min_+1));

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

using namespace std;

int n,q;
int a[100001],v[100001];
int val[1<<22],mid[1<<22];

void update(int a,int x){
	a+=(1<<21);
	val[a]+=x;
	while(a>0){
		a=(a-1)/2;
		val[a]=max(val[a*2+1],val[a*2+2]);
		if(val[a]==val[a*2+1])mid[a]=mid[a*2+1];
		else mid[a]=mid[a*2+2];
	}
}

int main(void){
	scanf("%d%d",&n,&q);
	for(int i=1<<21;i<(1<<22);i++)mid[i]=i-(1<<21);
	for(int i=0;i<q;i++){
		scanf("%d%d",&a[i],&v[i]);
		update(a[i]-1,v[i]);
		printf("%d %d\n",mid[0]+1,val[0]);
	}
	return 0;
}

Measured memory_bytes: 25336
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class CABSubstrings {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int cntAB = 0;
            int finA = 0;
            int staB = 0;
            int both = 0;
            for (int i = 0; i < n; i++) {
                String s = in.next();
                if (s.startsWith("B") && s.endsWith("A")) both++;
                else if (s.startsWith("B")) staB++;
                else if (s.endsWith("A")) finA++;
                cntAB += f(s);
            }
            out.println(staB + finA > 0 ? cntAB + Math.min(staB, finA) + both : cntAB + Math.max(both - 1, 0));
        }

        int f(String s) {
            // "AB"を数える
            int res = 0;
            for (int i = 0; i < s.length() - 1; i++) {
                if (s.charAt(i) == 'A' && s.charAt(i + 1) == 'B') res++;
            }
            return res;
        }

    }
}



Measured memory_bytes: 29180
def Main(A, B, C, K):
    if K < A:
        return K
    elif A <= K <= A+B:
        return A
    else:
        return 2*A+B-K
        
def main():
    A, B, C, K = map(int, input().split())
    print(Main(A, B, C, K))

if __name__ == '__main__':
    main()

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

typedef long long ll;
using namespace std;

int main(void) {
  int a, b; 
  cin >> a >> b;
  if (a <= 5) {
    cout << 0 << endl;
  }
  else if (a < 13) {
    cout << (b >> 1) << endl;
  }
  else {
    cout << b << endl;
  }
  return 0;
}

Measured memory_bytes: 256