akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys
import math
from bisect import bisect_left

# def func(A, B, x):
#     return math.floor(A*x/B) - A*math.floor(x/B)

def solve(A: int, B: int, N: int):
    def func(x):
        return math.floor(A/B * (x%B))

    leftmost = 1
    rightmost = min(N,B)
    midpoint = rightmost // 2
    
    midpoint = min(N,B-1)
    ans = math.floor(A*midpoint/B) - A*math.floor(midpoint/B)
    print(ans)

    # i = 0
    # over_N =0
    # while over_N < N:
    #     x = 10 * 10**i
    #     over_N = func(A, B, x)
    #     i += 1

    # while True:
    #     out = func(A, B, x)
    #     if  out <= N:
    #         break
    #     else:
    #         x -= 1

    # print(func(A, B, x))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9120
#include<iostream>

using namespace std;

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

int dp[60][60][60];

int main() {
  int n, m;
  cin >> n >> m;
  int a[n], b[n], c[n];
  rep (i, n) cin >> a[i] >> b[i] >> c[i];
  rep (i, 60) rep (j, 60) rep (k, 60) dp[i][j][k] = -1e9;
  dp[0][m][0] = 0;
  rep (i, n) rep (j, m + 1) rep (k, m + 1) rep (l, min(j + 1, 9)) {
    if (l + k <= 8 && l + k > 0) dp[i + 1][j - l][l] = max(dp[i + 1][j - l][l], dp[i][j][k] + a[i] * l + b[i] * k);
    if (l > 0) dp[i + 1][j - l][l] = max(dp[i + 1][j - l][l], dp[i][j][k] + a[i] * l);
    if (k > 0) dp[i + 1][j - l][l] = max(dp[i + 1][j - l][l], dp[i][j][k] + b[i] * k);
    if (l > 1) dp[i + 1][j - l][l] = max(dp[i + 1][j - l][l], dp[i][j][k] + a[i]);
    if (k > 1) dp[i + 1][j - l][l] = max(dp[i + 1][j - l][l], dp[i][j][k] + b[i]);
    dp[i + 1][j - l][l] = max(dp[i + 1][j - l][l], dp[i][j][k] + c[i]);
  }
  int res = -1e9;
  rep (i, m + 1) rep (j, m + 1) res = max(res, dp[n][i][j]);
  cout << res << endl;
}

Measured memory_bytes: 2004
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    int a,b;cin>>a>>b;
    if(a<=9&&b<=9)cout<<a*b<<endl;
    else cout<<-1<<endl;
}

Measured memory_bytes: 256
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k =MAP()

a = LIST()

# vis = [False]*n
# idx = 0
# temp = [a[0]-1]
# vis[a[0]-1] =True
i=0
j = 1
dd = defaultdict(int)
dd[1] = 0
while(True):
    if(a[i] in dd):
        pos = dd[a[i]]
        break
    dd[a[i]] = j
    i = a[i]-1
    j+=1

suited = list(dd.keys())[pos:]
temp = j-pos
if(k>=pos):
    k-=pos
    k = k%temp

    print(suited[k])
else:
    newS = list(dd.keys())[:pos]
    print(newS[k])

Measured memory_bytes: 111004
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  Int h,w;
  cin>>h>>w;
  Int c[10][10];
  Int inf=1e5;
  for(Int i=0;i<10;i++)
    for(Int j=0;j<10;j++){
      cin>>c[i][j];
      if(c[i][j]<0) c[i][j]=inf;
    }
  for(Int k=0;k<10;k++)
    for(Int i=0;i<10;i++)
      for(Int j=0;j<10;j++)
	c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
	
  Int ans=0;
  for(Int i=0;i<h;i++)
    for(Int j=0;j<w;j++){
      Int k;
      cin>>k;
      if(~k) ans+=c[k][1];
    }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
)

func main() {
	log.SetFlags(log.Lshortfile)
	N := nextInt()
	T := nextInt()
	c := make([]int, N)
	t := make([]int, N)
	for i := 0; i < N; i++ {
		c[i] = nextInt()
		t[i] = nextInt()
	}
	mincost := int(1e9)
	find := false
	for i := 0; i < N; i++ {
		if t[i] <= T && c[i] < mincost {
			mincost = c[i]
			find = true
		}
	}
	if !find {
		fmt.Println("TLE")
		return
	}
	fmt.Println(mincost)
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func minmax(a, b int) (int, int) {
	if a > b {
		return b, a
	}
	return a, b
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	return p[i].b < p[j].b
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}
func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}


Measured memory_bytes: 640
import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
N = len(S)

count = 0
DP = [[0] *  (N + 1) for _ in range(3)]
for i in range(1, N + 1):
    s = S[i - 1]
    if s == 'A':
        DP[0][i] = (DP[0][i - 1] + pow(3, count, MOD)) % MOD
        DP[1][i] = DP[1][i - 1]
        DP[2][i] = DP[2][i - 1]
    elif s == 'B':
        DP[0][i] = DP[0][i -1]
        DP[1][i] = (DP[1][i - 1] + DP[0][i - 1]) % MOD
        DP[2][i] = DP[2][i - 1]
    elif s == 'C':
        DP[0][i] = DP[0][i - 1]
        DP[1][i] = DP[1][i - 1]
        DP[2][i] = (DP[2][i - 1] + DP[1][i - 1]) % MOD
    else:
        DP[0][i] = (3 * DP[0][i - 1] + pow(3, count, MOD)) % MOD
        DP[1][i] = (3 * DP[1][i - 1] + DP[0][i - 1]) % MOD
        DP[2][i] = (3 * DP[2][i - 1] + DP[1][i - 1]) % MOD
        count += 1

print (DP[2][N])

# print (DP)

Measured memory_bytes: 15772
let cmp a b = if snd a = snd b then 0 else if snd a > snd b then 1 else -1

let () =
  let n = read_int () in
  let st = Array.init n (fun i -> Scanf.scanf " %d" (fun a -> (i + 1, a))) in
  Array.sort cmp st ;
  Array.iter (fun a -> Printf.printf "%d " (fst a)) st


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

using namespace std;

int ans = 0x3f3f3f3f,n;

int main()
{
	scanf("%d",&n);
	
	for(int i = 1 ; i <= n / 2 ; i++)
	{
		int a = i , b = n - i , s = 0;
		while(a)
		{
			s += a % 10;
			a /= 10;
		}
		while(b)
		{
			s += b % 10;
			b /= 10;
		}
		ans = min(ans,s);
	}
	
	printf("%d",ans);

	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 100000 + 10;
const long long MOD = 1000000007;

int N, M;
long long Z[MAXN];

void Work()
{
	Z[0] = 1;
	for (int i = 1; i < MAXN; i ++)
		Z[i] = (Z[i - 1] * (long long) i) % MOD;

	scanf("%d%d", &N, &M);
	if (N > M)
		swap(N, M);
	int Ans;
	if (N + 1 == M)
		Ans = (Z[N] * Z[M]) % MOD;
	else if (N == M)
	{
		Ans = (Z[N] * Z[M]) % MOD;
		Ans = (Ans + Ans) % MOD;
	}
	else
		Ans = 0;
	printf("%d\n", Ans);
}

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

Measured memory_bytes: 896
#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack> 
#include<vector>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
//const int MAX_V=105;
const long double pi = 3.14159265;
const long long mod =1e9+7;


int main(){
    int s, count =0;
    cin >> s;
    int i;
    for(i=0;i<3;i++){
        if(s%10==1){
            count += 1;
        }
        s/=10;
    }

    cout << count << endl;

    return 0;
}
 

Measured memory_bytes: 256
gets.scan(/(R+)(L+)/).each { |r,l|
  print '0 ' * (r.size - 1)
  print "#{(r.size+1)/2 + l.size/2} "
  print "#{r.size/2 + (l.size+1)/2} "
  print '0 ' * (l.size - 1)
}

Measured memory_bytes: 14204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  string color, number;
  number="Three";
  cin>>n;
  
  for(int i=0; i<n; i++) {
    cin>>color;
    if(color=="Y"){
      number="Four";
      break;
    }
  }
  cout << number << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(s) s.begin(),s.end()
#define pb push_back
#define uno unordered_map
#define pi 3.1415926536
#define dig(a) fixed<<setprecision(a)
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
ll power(ll a, ll n) {ll res = 1; while (n) {if (n % 2) {res *= a;} n >>= 1; a *= a;} return res;}
ll powerm(ll a, ll n, ll m) {ll res = 1; while (n) {if (n % 2) {res = (res * a) % m;} n >>= 1; a = (a * a) % m;} return res;}
const int M=1e9+7;
ll mod(ll x){
      return ((x%M + M)%M);
}
ll add(ll a, ll b){
      return mod(mod(a)+mod(b));
}
ll mul(ll a, ll b){
      return mod(mod(a)*mod(b));
}

int main(){
	fast();
	int test=1;
	//cin>>test;
	while(test--){
		ll a,b,c,d;
		cin>>a>>b>>c>>d;
		ll m1 = a*c, m2=a*d,m3=b*c,m4=b*d;
		ll ans = max(m1,max(m2,max(m3,m4)));
		cout<<ans;
	}
	return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <cmath>

using namespace std;

int main() {

  int n;
  int i,h,w;

  double bmi;
  int id;

  while(cin >> n) {

    if(n==0) break;

    bmi=100.0;

    for(int idx=0;idx<n;idx++) {

      cin >> i >> h >> w;

      if(fabs((double)w/((double)(h*h)/10000.0)-22.0)<fabs(bmi-22.0)) {

	id=i;

	bmi=(double)w/((double)(h*h)/10000.0);

      }

      else if(fabs((double)w/((double)(h*h)/10000.0)-22.0)==fabs(bmi-22.0)) {

	if(id>i) id=i;

	bmi=(double)w/((double)(h*h)/10000.0);

      }

      //cout << bmi << endl;

    }

    cout << id << endl;

  }

}

Measured memory_bytes: 0
import bisect
from collections import deque
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    dq = deque([])
    for A in As:
        idx = bisect.bisect_left(dq, A)
        if idx == 0:
            dq.appendleft(A)
        else:
            dq[idx - 1] = A
    print(len(dq))


if __name__ == "__main__":
    main()


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

using namespace std;

int main() {
	int N;

	cin >> N;

	vector<int> a(N);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}

	sort(a.begin(), a.end(), greater<int>());

	int Alice = 0, Bob = 0;
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) Alice += a[i];
		else Bob += a[i];
	}

	cout << Alice - Bob << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, X;
  cin >> N >> X;
  vector<int> vec(N);
   for (int i = 0; i < N; i++) {
     cin >> vec.at(i);
   }
  int a = 0;
   for (int i = 0; i < N; i++) {
     a += vec.at(i);
   }
  int b = vec.at(0);
   for (int i = 0; i < N; i++) {
     if (vec.at(i) < b)
       b = vec.at(i);
   }
  cout << N + (X - a) / b << endl;
}

Measured memory_bytes: 3600
# 解説
# 「右隣がCであるようなA」を数えた方が単純

def main():
    import sys
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    s = input().rstrip()

    imos = [0] * (N + 1)
    for i in range(N - 1):
        if s[i:i + 2] == 'AC':
            imos[i + 1] += 1  # Aの位置に加算
    for i in range(N):
        imos[i + 1] += imos[i]

    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        t = imos[r - 1] - imos[l - 1]
        # rの端から1文字手前までの右にCを持つAの個数を調べる
        # r-1==そのようなAのときr==C
        ans.append(t)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 13456
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n[2000000][2],r[2000],c[2000],H,W,R,K,LEFT,RIGHT,MID,S;
int main(){
	while(true){r[0]=0;c[0]=0;S=0;memset(n,0,sizeof(n));
	cin>>H>>W;if(H==0 && W==0){break;}
	for(int i=1;i<=H;i++){cin>>R;r[i]=r[i-1]+R;}
	for(int i=1;i<=W;i++){cin>>R;c[i]=c[i-1]+R;}
	for(int i=0;i<=H;i++){for(int j=i+1;j<=H;j++){n[r[j]-r[i]][0]++;}}
	for(int i=0;i<=W;i++){for(int j=i+1;j<=W;j++){n[c[j]-c[i]][1]++;}}
	for(int i=1;i<2000000;i++){S+=n[i][0]*n[i][1];}
	cout<<S<<endl;}
}

Measured memory_bytes: 16808
import sys

input = sys.stdin.readline


def calc_divisors(n):
    divisors_a = []
    divisors_b = []
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            divisors_a.append(d)
            if n // d != d:
                divisors_b.append(n // d)
    divisors = divisors_a + divisors_b[::-1]
    return divisors


def main():
    N, M = map(int, input().split())

    divisors = calc_divisors(M)
    ans = 0
    for divisor in divisors:
        if M // divisor >= N:
            ans = max(ans, divisor)

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9444
// Hack it and have it ;) //
/*author* Priyanshu Shrivastav (from IIT Palakkad) *
 * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
 * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
 * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
 * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
When I wrote this, only God and I understood what I was doing
 ** * * * * * * * Now, only God knows * * * * * * */
#include      <bits/stdc++.h>
#include      <ext/pb_ds/assoc_container.hpp>
#include      <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC   optimize ("Ofast")
#pragma GCC   optimize ("unroll-loops")
#pragma GCC   target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS   ios_base::sync_with_stdio(false); cin.tie (nullptr)
#define PREC  cout.precision (10); cout << fixed
#define x     first
#define y     second
#define bg(x) " [ " << #x << " : " << (x) << " ] "
#define un(x) sort(x.begin(), x.end()), \
              x.erase(unique(x.begin(), x.end()), x.end())
using   ll  = long long;
using   ull = unsigned long long;
using   ff  = long double;
using   pii = pair<int,int>;
using   pil = pair<int,ll>;
typedef tree
< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;

struct chash {
   int operator()(pii x) const { return x.x*31 + x.y; }
};
gp_hash_table <pii, int, chash> mp;

seed_seq seq{
   (uint64_t) chrono::duration_cast<chrono::nanoseconds>
      (chrono::high_resolution_clock::now().time_since_epoch()).count(),
      (uint64_t) __builtin_ia32_rdtsc(),
      (uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq); //uniform_int_distribution<int> (l, h)(rng); //[low, high]

#define debug(args...) { \
   /* WARNING : do NOT compile this debug func calls with following flags: // \
    * // -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2*/ \
   string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
   stringstream _ss(_s); \
   istream_iterator<string> _it(_ss); err(_it, args); \
}
void err(istream_iterator<string> it) {
   it->empty(); cerr << " (Line : " << __LINE__ << ")" << '\n';
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
   cerr << fixed << setprecision(15)
      << " [ " <<  *it << " : " << a  << " ] "<< ' ';
   err(++it, args...);
}
/*****************************************************************************/

struct job {
   int deadline, len;
   bool operator < (const job &o) const {
      return deadline < o.deadline || (deadline == o.deadline && len < o.len);
   }
};
vector <job> jobs;
int n;

signed main() {
   IOS; PREC;
   cin >> n;
   for (int i = 0; i < n; ++i) {
      int x, y;
      cin >> x >> y;
      jobs.push_back({y, x});
   }

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

   int cur_time = 0;

   bool ok = true;
   for (int i = 0; i < n; ++i) {
      if (cur_time > jobs[i].deadline || cur_time + jobs[i].len > jobs[i].deadline) {
         ok = false;
         break;
      }
      cur_time = cur_time + jobs[i].len;
   }
   cout << (ok ? "Yes\n" : "No\n");
   return EXIT_SUCCESS;
}


Measured memory_bytes: 2420
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n,m;
bool f[22][22];
char c[] = {"NESW"};
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int main(void)
{
  while(1){
    cin >> n;
    if(!n) break;
    memset(f,false,sizeof(f));
    for(int i = 0; i < n; i++){
      int x,y;
      cin >> x >> y;
      f[x][y] = true;
    }
    cin >> m;

    int x = 10;
    int y = 10;
    int ret = 0;
    for(int i = 0; i < m; i++){
      char d;
      int l;
      cin >> d >> l;
      for(int j = 0; j < 4; j++){
	if(d != c[j]) continue;
	for(int k = 0; k < l; k++){
	  x += dx[j];
	  y += dy[j];
	  if(f[x][y]){
	    ret++;
	    f[x][y] = false;
	  }
	}
      }
    }
    cout << ((ret == n)?"Yes":"No") << endl;
  }
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    int n, m;
    cin >> n >> m;
    cout << n * (n-1)/2 + m * (m-1)/2 << endl;
}

Measured memory_bytes: 256
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdio.h>


using namespace std;

int main(void) {
    int a,b;
    cin>>a>>b;

    int ans=(b-a)*(b-a+1)/2-b;

    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);


int c[6] = {1, 5, 10, 50, 100, 500};
int a[6];
signed main(){
  int n = 6;
  rep(i,n)cin >> a[i];
  int ans = 0;
  rep(i,n)ans += a[i] * c[i];
  cout << (ans >= 1000) << endl;
  return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(), v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 1;
vector<int> g[N];
vector<int> vis(N);
void solve(){
    int n;
    cin >> n;
    int a[n];
    deque<int> dq;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i % 2){
            dq.push_front(a[i]);
        }else{
            dq.push_back(a[i]);
        }
    }
    vector<int> ans;
    while(dq.size()){
        ans.push_back(dq.back());
        dq.pop_back();
    }
    if(n % 2 == 0){
        reverse(ans.begin(), ans.end());
    }
    for(int &i : ans){
        cout << i << ' ';
    }
    cout << '\n';
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        solve();
    }
}

Measured memory_bytes: 39728
INF = 1<<31
V, E = map(int, raw_input().split())
l = [[INF]*V for i in range(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            if l[i][k] != INF and l[k][j] != INF:
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print "NEGATIVE CYCLE"
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF: r[i] = "INF"
        print " ".join(map(str, r))

Measured memory_bytes: 6856
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

using System.Collections;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        var otoshidamaList = Enumerable.Range(0, N)
            .Select(n => Console.ReadLine().Split(' '))
            .Select(arr => new { x = double.Parse(arr[0]), u = arr[1] })
            .ToList();

        var ans = otoshidamaList.Select(itm => itm.u == "JPY" ? itm.x : itm.x * 380000.0).Sum();

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define tc() int t; cin>>t; while(t--)
#define print(n) cout<<n<<"\n"
#define inp(n) int n; cin>>n
#define all(cont) cont.begin(), cont.end()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define maxn 1000010
#define f  first
#define s  second
#define fora(var, start, end) for(int var = start; var < end; var++)
int main()
{
  inp(n);
  vector<int> v(n);
  for(int &a : v)cin>>a;
  vector<int> dp(n);
  dp[0]=0;
  dp[1]=abs(v[0]-v[1]);
  fora(i,2,n)
  {
    dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]), dp[i-2]+abs(v[i]-v[i-2]));
  }
  cout<<dp[n-1];
  return 0;
}

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

int main(){
    int W,H,x,y,r;
    cin>>W>>H>>x>>y>>r;
    if(x>=r&&y>=r&&x+r<=W&&y+r<=H){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3120
#include <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if(b==0)return 1;
  if ((a == 0)||(mod!=-1&&(a+mod)%mod==0)) {
    return 0;
  }
  long long x = 1;
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}

// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P=std::pair<long long,long long>;

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

  ll h,n;
  std::cin>>h>>n;

  std::vector<P> mag(n);
  rep(i,0,n)std::cin>>mag[i].first>>mag[i].second;

  std::vector<ll> dp(h+10,std::numeric_limits<ll>::max());
  dp[0]=0;

  rep(i,1,h+10){
    rep(j,0,n){
      if(mag[j].first>=i)chmin(dp[i],mag[j].second);
      else chmin(dp[i],dp[i-mag[j].first]+mag[j].second);
    }
  }

  std::cout<<dp[h]<<"\n";

  return 0;
}


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

#define F first
#define S second
#define int long long
#define pb push_back
#define endl '\n'

using namespace std;
 
int32_t main()
{
	ios_base :: sync_with_stdio(false) ;
	cin.tie(0); cout.tie(0) ;
	string a , b ;
	cin >> a >> b ;
	int n = a.size() ;
	int m = b.size() ; 
	int dp[n + 1][m + 1] ; 
	memset(dp , 0 , sizeof dp) ; 
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			if(a[i - 1] == b[j - 1]){
				dp[i][j] = dp[i - 1][j - 1] + 1 ;
			}
			else{
				dp[i][j] = max(dp[i - 1][j] , dp[i][j -1]) ; 
			}
		}
	}
	int x = n , y = m ; 
	string ans = "" ;
	while(x >= 1 and y >= 1){
		if(a[x - 1] == b[y - 1]){
			ans += a[x - 1] ; 
			x-- ; 
			y-- ; 
		}
		else{
			if(dp[x - 1][y] >= dp[x][y - 1]) x-- ; 
			else y-- ; 
		}
	}
	reverse(ans.begin() , ans.end()) ; 
	cout << ans << endl ; 
	return 0 ;
}



Measured memory_bytes: 70656
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define mod 1000000007
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
const int maxn=100005;
using namespace std;
int n,k,ans=1,tot,head[maxn];
struct Edge{
  int To,Next;
}ed[maxn*2];
void addedge(int u,int v){
  ed[++tot].Next=head[u];head[u]=tot;ed[tot].To=v;
}
int son[maxn],fa[maxn];
void dfs(int x,int pre){
//  cout<<ans<<endl;
  //son[x]=1;
  ans=1ll*ans*(k-son[fa[x]])%mod;
  if(x!=1)son[x]=1;
  for(int i=head[x];i;i=ed[i].Next){
    int v=ed[i].To;
    if(v==pre)continue;
    fa[v]=x;son[x]++;
    dfs(v,x);
  }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
      int x,y;cin>>x>>y;
      addedge(x,y);addedge(y,x);
    }
    dfs(1,0);
    /*for(int i=1;i<=n;i++){
      ans=1ll*ans*(k-son[fa[i]])%mod;
    }
    */
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
vector <int> V;
int n,a;
int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        if(i%2)V.push_back(a);
        else V.insert(V.begin(),a);
    }
    
    if(n%2){
        for(auto it=V.begin();it!=V.end();it++)
            cout<<(it==V.begin()?"":" ")<<*it;
    }else{
        for(auto it=V.end()-1;it>=V.begin();it--)
        cout<<(it==V.end()-1?"":" ")<<*it;
    }
    cout<<"\n";
    
    
    return 0;
}


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <utility>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF=1<<29;
ll mod=1000000007;

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

	int a;
	string s;
	cin>>a>>s;
	if(a>=3200) cout<<s<<endl;
	else cout<<"red"<<endl;


	return 0;
}


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

def rec(x,memo,a,b,c,d):
    if x in memo:
        return memo[x]
    
    ans=x*d
    ans=min(ans,rec(x//2,memo,a,b,c,d)+a+(x%2)*d)
    ans=min(ans,rec((x+1)//2,memo,a,b,c,d)+a+((x+1)//2*2-x)*d)
    ans=min(ans,rec(x//3,memo,a,b,c,d)+b+(x%3)*d)
    ans=min(ans,rec((x+2)//3,memo,a,b,c,d)+b+((x+2)//3*3-x)*d)
    ans=min(ans,rec(x//5,memo,a,b,c,d)+c+(x%5)*d)
    ans=min(ans,rec((x+4)//5,memo,a,b,c,d)+c+((x+4)//5*5-x)*d)

    memo[x]=ans
    return ans

for _ in range(t):
    n,a,b,c,d=list(map(int,input().split()))
    memo={0:0,1:d}
    print(rec(n,memo,a,b,c,d))

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

struct Edge {
	ll to;
    ll cost;
};

struct edge {
    ll from;
    ll to;
    ll cost;
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<edge>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define mp make_pair
#define pb push_back
/***** define constant start *******/
const int MAX = 10000000;
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = 1LL << 60;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
/****** define constant end ********/

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

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

void debug_out() { std::cout << std::endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << H << " ";
    debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0)
        res += m;
    return res;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1)
        res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
	    a -= t * b;
        swap(a, b);
	    u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}
/****** define variable start ******/
string s;
/******* define variable end *******/
int solve() {
	cin >> s;
	if(s.substr(s.size()-1, 1) == "s"){
		cout << s << "es" << endl;
	}else{
		cout << s << "s" << endl;
	}
    return 0;
}

int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define LLI long long int
#define pii pair<int,int>
#define fst first
#define sec second
#define ULTRA 2134567890
#define de(x) if(x!=0 && MODE==x)
#define MODE 0
using namespace std;

char S[200007];
int cnt[2019] = {};

int main()
{
    int i,j;

    scanf("%s", S);

    int N = strlen(S);

    LLI ans = 0;
    int r = 0;
    int mul = 1;
    for( i = N-1; i>=0; i--)
    {
        r = ( r + mul * ( S[i] - '0') ) % 2019;
        mul = mul * 10 % 2019;

        de(1) printf("r = %d\n", r);

        if( r == 0)
        {
            ans += cnt[r] + 1;
        }
        else
        {
            ans += cnt[r];
        }

        cnt[r]++;
    }

    printf("%lld\n", ans);

    return 0;
}

//
//          ___ ___  __________  __________
//         /////\  \/\   ______\/\\\\\\\\\\\  Code by ~Ice Tea~ of
//        //// \ \  \ \  \_____/\ \\\\_____/      New Empire of CHSH ...
//       ////   \ \  \ \  \      \ \\\\\\\\\\\
//      ////__   \ \  \ \  \      \ \\\\_____/
//     ///////\   \ \  \ \  \______\ \\\\_______   ________
//    ////____/    \ \__\ \___   ___\ \\\\\\\\\\\ _\  ___  \_
//   /__/           \/__/\/__/\  \__/\ \\\\_____//\  .\_/\_  \
//                           \ \  \   \ \\\\\\\\\\\\  \_\/_\  \
// ... with the AC Power of   \ \  \   \ \\\\_____/ \   _____  \
//   The Great Tsundere Doggy. \ \  \   \ \\\\     \ \  \  \ \  \
//                              \ \__\   \ \\\\\\\\\\ \__\  \ \__\
//                               \/__/    \/________/\/__/   \/__/
//


Measured memory_bytes: 3928
#include<bits/stdc++.h>
using namespace std;
int main(){
    long xs,ys,xt,yt;
    cin >> xs>>ys>>xt>>yt;
    int n;
    cin >> n;
    long x[n];
    long y[n];
    long r[n];
    for(int i=0;i<n;i++)cin >> x[i]>>y[i]>>r[i];
    double beem[n+2][n+2];
    beem[0][0] = 0.0;
    beem[n+1][n+1] = 0.0;
    beem[0][n+1] = sqrt((double)((xs-xt)*(xs-xt) + (ys-yt)*(ys-yt)));
    beem[n+1][0] = sqrt((double)((xs-xt)*(xs-xt) + (ys-yt)*(ys-yt)));
    for(int i=1;i<=n;i++){
        beem[0][i] = max(sqrt((double)((x[i-1]-xs)*(x[i-1]-xs)+(y[i-1]-ys)*(y[i-1]-ys))) - r[i-1],0.0);
        beem[n+1][i] = max(0.0,sqrt((double)((x[i-1]-xt)*(x[i-1]-xt)+(y[i-1]-yt)*(y[i-1]-yt)))-r[i-1]);

        beem[i][0] = beem[0][i];
        beem[i][n+1] = beem[n+1][i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                beem[i][j] = 0.0;
            }else{
                beem[i][j] = max(sqrt((double)((x[i-1]-x[j-1])*(x[i-1]-x[j-1])+(y[i-1]-y[j-1])*(y[i-1]-y[j-1]))) - r[i-1]-r[j-1],0.0);
            }
        }
    }
    vector<double>distance(n+2,1.0e+12);

    // for(int i=0;i<=n+1;i++){
    //     for(int j=0;j<=n+1;j++){
    //         printf("%d %d: %lf\n",i,j,beem[i][j]);
    //     }
    // }

    
    priority_queue<pair<double,int> ,vector<pair<double,int> >, greater<pair<double,int> > >que;
    que.push(make_pair(0.0,0));

    while(!que.empty()){
        double dist = que.top().first;
        int now = que.top().second;
        que.pop();

        // cout << now << " "<<dist << endl;
        if(distance[now] > dist){
            distance[now] = dist;
        }else{
            continue;
        }
        // distance[now] = min(dist,distance[now]);

        for(int i=1;i<=n+1;i++){
            if(i!=now && dist + beem[now][i] < distance[i]){
                que.push(make_pair(dist + beem[now][i],i));
            }
        }
    }
    printf("%.10lf\n",distance[n+1]);
    

}

Measured memory_bytes: 18288
x1, y1, x2, y2 = gets.chomp.split(' ').map(&:to_i)

x3 = x2 + (y1 - y2)
y3 = y2 + (x2 - x1)

x4 = x3 + (y2 - y3)
y4 = y3 + (x3 - x2)

puts "#{x3} #{y3} #{x4} #{y4}"


Measured memory_bytes: 1788
import java.util.Scanner;

//Sorting Five Numbers
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a[] = new int[5];
		for(int i=0;i<5;i++)a[i]=sc.nextInt();
		for(int i=0;i<4;i++){
			int m = i;
			for(int j=i+1;j<5;j++){
				if(a[j]>a[m])m=j;
			}
			int t = a[i];
			a[i]=a[m];
			a[m]=t;
		}
		for(int i=0;i<4;i++)System.out.print(a[i]+" ");
		System.out.println(a[4]);
	}
}

Measured memory_bytes: 11000
#pragma warning(disable:4996)

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <cmath>
#include <map>
#include <array>
#include <set>
#include <queue>
#include <complex>
#include <iterator>
#include <random>
#include <time.h>
#include <tuple>
#include <functional>
#include <list>
#include <limits.h>
#define mp make_pair
#define ni(x) scanf("%d", &(x))
#define nii(x,y) scanf("%d%d",&(x),&(y))
#define mul(x,y) ((ll)(x)*(y)%mod)
#define mtp make_tuple
#define F(i,n) for(int i = 0; i < (n); i++)
#define FF(i,n) for(int i = 1; i <= (n); i++)
#define FE(i,n) for(int i = 0; i <= (n); i++)

#ifndef __GNUG__
int __builtin_popcount(int n) {
	int x = 0;
	while (n)n -= n&(-n), x++;
	return x;
}
#endif

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int mod = 1000000007;
const int inf = 2012345678;
const ll infl = 9012345678901234567;
const double pi = 3.1415926535897932384626433832795;
//----------------------------------------------------------------------------//

const int N = 10101;
vector<int> adj[N];
int chk[N], dg[N], c[N], ans[N], M;

int main() {
#ifndef __GNUG__
	freopen("input.txt", "r", stdin);
#endif
	int n; ni(n);
	F(i, n - 1) {
		int u, v; nii(u, v); u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	F(i, n)dg[i] = adj[i].size();
	F(i, n)ni(c[i]);
	sort(c, c + n);
	F(i, n) {
		int x = -1;
		F(j, n) {
			if (chk[j])continue;
			if (x == -1 || dg[j] < dg[x])x = j;
		}
		M += dg[x] * c[i];
		chk[x] = 1;
		ans[x] = c[i];
		for (auto &y : adj[x])dg[y]--;
	}
	printf("%d\n", M);
	F(i, n)printf("%d ", ans[i]); puts("");
	
	return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
//const int inf = 1e9 + 7;

int main() {
    int n; cin >> n;
    map<ll, ll> mp;
    mp[0]++;
    ll sum = 0;
    rep(i, n) {
        int a; cin >> a;
        sum += a;
        mp[sum]++;
    }
    sum = 0;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        sum += it->second * (it->second - 1) / 2;
    }
    cout << sum << endl;
}







Measured memory_bytes: 12800
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _node{
    struct _node *prev;
    int key;
    struct _node *next;
}node;

node* init_dll(node* tail){
    tail = malloc(sizeof(node));
    tail -> prev = tail;
    tail -> next = tail;
    return tail;
}

node* insert_beg(node* tail, int n){
    node* new_node = malloc(sizeof(node));
    if(tail->next==tail){
        new_node -> prev = tail;
        new_node -> key = n;
        new_node -> next = tail;
        tail -> prev = new_node;
        tail -> next = new_node;
    }
    else{
        node* head = tail->next;
        new_node -> prev = tail;
        new_node -> key = n;
        new_node -> next = head;
        head -> prev = new_node;
        tail -> next = new_node;
    }
    return tail;
}

node* del_first(node* tail){
    node* head = tail->next;
    if(head -> next == tail){//difference between = and == !
        tail->next = tail;
        tail->prev = tail;
    }
    else{
        head -> next -> prev = tail;
        tail -> next = head -> next;
    }
    free(head);
    return tail;
}

node* del_last(node* tail){
    node* last = tail->prev;
    if(last -> prev == tail){
        tail->next = tail;
        tail->prev = tail;
    }
    else{
        tail -> prev = last -> prev;
        last -> prev -> next = tail;
    }
    free(last);
    return tail;
}

node* del_node(node* tail, int n){
    node* ptr = tail->next;
    while(ptr->key!=n){
        if(ptr==tail)
            return tail;
        ptr = ptr -> next;
    }
    if(ptr == tail -> next){
        ptr -> next -> prev = tail;
        tail -> next = ptr -> next;
    }
    else if(ptr == tail->prev){
        ptr -> prev -> next = tail;
        tail -> prev = ptr -> prev;
    }
    else{
        ptr -> prev -> next = ptr -> next;
        ptr -> next -> prev = ptr -> prev;
    }
    free(ptr);
    return tail;
}

void display(node* tail){
    node* ptr = tail -> next;
    if(ptr==tail){
        printf("\n");
        return;
    }
    while(ptr!=tail){
        if(ptr->next == tail){
            printf("%d\n", ptr->key);
            break;
        }
        printf("%d ", ptr->key);
        ptr = ptr -> next;
    }
    return;
}

int main(){

    int op_num;
    scanf("%d", &op_num);
    node* tail; 
    tail = init_dll(tail);
    while(op_num--){
        char instr[20];
        int data;
        scanf("%s", instr);
        if(strcmp(instr,"insert")==0){
            scanf("%d", &data);
            tail = insert_beg(tail, data);
    //display(tail);
        }
        else if(strcmp(instr,"delete")==0){
            scanf("%d", &data);
            tail = del_node(tail, data);
    //display(tail);
        }
        else if(strcmp(instr,"deleteFirst")==0){
            tail = del_first(tail);
    //display(tail);
        }
        else if(strcmp(instr,"deleteLast")==0){
            tail = del_last(tail);
    //display(tail);
        }
    }
    display(tail);
}



Measured memory_bytes: 33100
import bisect
n, k = map(int, input().split())
ab = sorted(map(lambda x: (int(x[0]), int(x[1])), [(input().split()) for _ in range(n)]))
cnt = []
s = 0
for i in range(n):
    cnt.append(ab[i][1] + s)
    s += ab[i][1]
# print(cnt)

print(ab[bisect.bisect_left(cnt, k)][0])


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

using namespace std;

struct Stick {
    int p, q, r, b;
    Stick() {}
    Stick(int pp, int qq, int rr, int bb) : p(pp), q(qq), r(rr), b(bb) {}
};

int gcd(int a, int b) {
    if(a < b) return gcd(b, a);
    while(true) {
        int tmp = a % b;
        a = b;
        b = tmp;
        if(b == 0) break;
    }
    return a;
}

int dfs(vector<Stick> &sticks, int pos) {
    int wr = 1, wb = 1;
    if(sticks[pos].r != 0) wr = dfs(sticks, sticks[pos].r);
    if(sticks[pos].b != 0) wb = dfs(sticks, sticks[pos].b);

    int mr = wr*sticks[pos].p;
    int mb = wb*sticks[pos].q;
    int g = gcd(mr, mb);
    return wr*(mb/g) + wb*(mr/g);
}

int main() {
    while(true) {
        int n;
        cin >> n;
        if(!n) break;

        vector<Stick> sticks(n+1);
        vector<bool> is_child(n+1, false);
        for(int i = 0; i < n; ++i) {
            int p, q, r, b;
            cin >> p >> q >> r >> b;
            sticks[i+1] = Stick(p, q, r, b);
            is_child[r] = is_child[b] = true;
        }

        int start = 1;
        while(is_child[start]) ++start;
        cout << dfs(sticks, start) << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    ll K;
    cin >> N >> K;
    vll H(N);
    rep(i, N) cin >> H[i];
    sort(H.begin(), H.end(), greater<ll>());
    
    ll ans = 0;
    rep(i, N) {
        if (i >= K) ans += H[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

int a[100];

int main(void){
    int i,n;

    scanf("%d",&n);

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

    for(i = n - 1;i >= 0;i--){
        printf("%d",a[i]);
        if(i > 0)
            printf(" ");
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		while(true){

			String[] exp = sc.nextLine().split(" ");
			int a = Integer.parseInt(exp[0]);
			int b = Integer.parseInt(exp[2]);

			if("+".equals(exp[1])){
				System.out.println(a + b);
			}else if("-".equals(exp[1])){
				System.out.println(a - b);
			}else if("*".equals(exp[1])){
				System.out.println(a * b);
			}else if("/".equals(exp[1])){
				System.out.println(a / b);
			}else if("?".equals(exp[1])){
				break;
			}
		}
	}
}

Measured memory_bytes: 17328
#include<bits/stdc++.h>
using namespace std;
int a[4];
int main(){
	int i,k,mx=0,s=0,pos=0;
	for(i=1;i<=3;i++){
		cin>>a[i];
		if(a[i]>mx){
			mx=a[i];
			pos=i;
		}
	}
	cin>>k;
	for(i=1;i<=3;i++){
		if(i!=pos) s+=a[i];
	}
	for(i=1;i<=k;i++){
		mx*=2;
	}
	s+=mx;
	cout<<s;
	return 0;
}

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

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

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

const int MAX = 1e5 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int N, A[MAX], B[MAX];

int main(){
    cin >> N;
    rep(i, N) cin >> A[i] >> B[i];

    vector<tuple<int, int, int>> v(N);
    rep(i, N) v[i] = make_tuple(A[i] + B[i], A[i], B[i]);

    sort(v.begin(), v.end(), greater<tuple<int, int, int>>());

    ll t = 0, a = 0;
    rep(i, N) {
        if (i % 2 == 0) t += get<1>(v[i]);
        else a += get<2>(v[i]);
    }

    cout << t - a << endl;
}

Measured memory_bytes: 2176
#include<stdio.h>

int main(void){

int R, G, B, N, r, g;
int count = 0;

scanf("%d", &R);
scanf("%d", &G);
scanf("%d", &B);
scanf("%d", &N);


for(r = 0; r <= N/R; r++){
    for(g = 0; g <= (N-R*r)/G; g++){
        if((N - R*r - G*g) % B == 0)
        count += 1;
    }
}


printf("%d\n", count);


return 0;
}


Measured memory_bytes: 128
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int get_ans(int x,int y)
{
    if (x>y) swap(x,y);
    if (x==y) return (x-1)*2;
    int k=(int)sqrt((long long)x*y);
    int ans=(k-1)*2-1;
    if ((long long)k*k<(long long)x*y)
    {
        ans++;
    }
    if ((long long)k*(k+1)<(long long)x*y)
    {
        ans++;
    }
    return ans;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",get_ans(x,y));
    }
    return 0;
} 


Measured memory_bytes: 256