akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
typedef pair <int, int> P;

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

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

    int h, w;
    cin >> h >> w;

    string s[1005];
    for (int i = 0; i < h; i++) cin >> s[i];

    priority_queue <P, vector<P>, greater<P>> q;
    int c[h][w];
    fill(c[0], c[h], 1e9);

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '#') {
                q.push(P(0, i * w + j));
                c[i][j] = 0;
            }
        }
    }

    while (q.size()) {
        P p = q.top();
        q.pop();

        int cost = p.first;
        if (cost > c[p.second / w][p.second % w]) continue;

        for (int i = 0; i < 4; i++) {
            int x = p.second / w + dx[i];
            int y = p.second % w + dy[i];
            if (x < 0 || x >= h || y < 0 || y >= w) continue;

            if (c[x][y] > cost + 1) {
                c[x][y] = cost + 1;
                q.push(P(cost + 1, x * w + y));
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            ans = max(ans, c[i][j]);
        }
    }

    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 15084
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n,k = list(map(int,input().split()))

#1~nについて考える
#1~nのうちi (modk) の個数の配列を作成
quotient = n//k
modk_cnt = [quotient for i in range(k)]
for i in range(n%k):
    modk_cnt[i+1]+=1

ret = modk_cnt[0]**3
if k%2==0:
    ret += modk_cnt[k//2]**3

print(ret)

Measured memory_bytes: 4632
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	c := make([][]int, 3)
	for i := range c {
		c[i] = make([]int, 3)
		for j := range c[i] {
			c[i][j] = readInt()
		}
	}

	for i := 0; i+1 < 3; i++ {
		d := c[i][0] - c[i+1][0]
		for j := 1; j < 3; j++ {
			if c[i][j]-c[i+1][j] != d {
				println("No")
				return
			}
		}
		d = c[0][i] - c[0][i+1]
		for j := 1; j < 3; j++ {
			if c[j][i]-c[j][i+1] != d {
				println("No")
				return
			}
		}
	}
	println("Yes")
}


Measured memory_bytes: 640
import java.util.*;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.io.*;

public class Main {
    public static void main(final String[] args) {
        final FastScanner scanner = new FastScanner();
        try (final FastWriter writer = new FastWriter()) {
            String S = scanner.next(), T = scanner.next();
            int A = scanner.nextInt(), B = scanner.nextInt();
            String U = scanner.next();
            if (S.equals(U)) A--;
            else B--;
            writer.printf("%d %d\n", A, B);
        }
    }
}

class FastScanner {
    private final BufferedReader br;
    private StringTokenizer st;

    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (final IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (final IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

class FastWriter extends PrintWriter {
    public FastWriter() {
        super(new BufferedOutputStream(System.out));
    }

    public static void main(final String[] args) {
        try (final FastWriter w = new FastWriter()) {
            w.println(32);
        }
    }
}



Measured memory_bytes: 23508
while 1:
  H,W = map(int,input().split())
  if H == W == 0:
    break
  else:
    for i in range(H):
      for j in range(W):
        if  i == 0  or j == 0:
          print("#",end='')
        elif i == H-1 or j == W-1:
          print("#",end='')
        else:
          print(".",end='')
      print()
    print()


Measured memory_bytes: 7004
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef long long ll;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define swap(a,b) {ll tp=a;a=b;b=tp;}
int upcmpii(const void *a,const void *b)
{return(*(int*)a==*(int*)b?0:(*(int*)a>*(int*)b?1:-1));}
void sort_ui(int *a,int n){qsort(a,n,sizeof(int),upcmpii);}
const ll MOD = 1000000007;

int my_upper_bound(int *p, int trg, int n){
    if(p[0] > trg) return 0;
    if(p[n-1] <= trg) return n;
    int left = 0, right = n-1;
    while(right - left > 1){
        int mid = (right + left)/2;
        if(p[mid] > trg) right = mid;
        else left = mid;
    }
    return right;
}

int main(){
    int A[101010],B[101010],C[101010];
    int n; scanf("%d",&n);
    rep(i,n) scanf("%d", A+i);
    rep(i,n) scanf("%d", B+i);
    rep(i,n) scanf("%d", C+i);

    sort_ui(A,n);sort_ui(B,n);sort_ui(C,n);
    ll ans[101010] = {0}, num = 0;
    rep(i,n){
        ans[i] = (n-my_upper_bound(C,B[i],n));
        //printf("%d ", ans[i]);
    }
    rep(i,n-1){
        ans[n-1-i-1] += ans[n-1-i];
    }
    rep(i,n){
        int tmp = my_upper_bound(B,A[i],n);
        if(tmp < n){
            num += ans[tmp];
        }
    }
    printf("%lld\n", num);
}

Measured memory_bytes: 4060
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]
A.sort(reverse=True)

dp = [[0] * (N + 1) for _ in range(N + 1)]

for s, (a, i) in enumerate(A):
    for l in range(s + 1):
        r = s - l
        L = dp[l][r] + a * (i - (l + 1))
        R = dp[l][r] + a * (N - r - i)

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

ans = 0
for i in range(N + 1):
    ans = max(ans, dp[i][N - i])
print(ans)


Measured memory_bytes: 96336
#include<stdio.h>
int main()
{
	int h, w, i, j;
	while (1)
	{
		scanf("%d %d", &h, &w);
		if ((h == 0) && (w == 0))
			break;
		for (i = 0; i < h; i++)
		{
			if ((i == 0) || (i == h - 1)){
				for (j = 0; j < w; j++)
					printf("#");
				printf("\n");
			}
			else{
				for (j = 0; j < w; j++){
					if ((j == 0) || (j == w - 1))
						printf("#");
					else
						printf(".");
				}
				printf("\n");
			}
		}
		printf("\n");

	}

	return(0);

}

Measured memory_bytes: 572
"use strict"

function main(input) {
  const N = ~~input
  const cake = 4
  const donut = 7
  // let ans;

  for (let i = 0; i <= N / cake; i++) {
    for (let j = 0; j <= N / donut; j++) {
      if (cake * i + donut * j === N) {
        console.log("Yes")
        return false
      }
    }
  }

  console.log("No")
}

main(require("fs").readFileSync("/dev/stdin", "utf8"))


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

long long s(long n){
  return n * (n+1) / 2;
}

int main(){
  int n;
  cin >> n;
  long long ans = 0;
  for (long i=1;i<n+1;i++) {
    ans += i*s(n/i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <stdlib.h>
int N,K,cnt;
int A[101][101];
int d[101], snuke[101];
int main(void) {
	scanf("%d %d", &N, &K);
	for(int j = 0; j < K; j++){
		scanf("%d", &d[j]);
		for(int i = 0; i < d[j]; i++){
			scanf("%d", &A[j][i]);
			int tmp = A[j][i];
		}
	}
	cnt = N;
	for(int k = 1; k <= N;k++){
		for(int j = 0; j < K; j++){
			for(int i = 0; i < d[j]; i++){
				int tmp = A[j][i];
				if(tmp == k){
					cnt--;
					j = K;
					i = d[j];
				}
			}
		}
	}

	printf("%d", cnt);

	return 0;
}

Measured memory_bytes: 1764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
const int INF = 1001001001;

template<class Type>
Type modpow(Type a, Type n, Type mod)
{
	Type res = 1;
	while (0 < n) {
		if (n & 1) {
			res = res * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

template<class Type>
Type gcd(Type x, Type y)
{
	Type r;
	if (x < y) swap(x, y);

	while (0 < y) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

template<class Type>
Type lcm(Type x, Type y)
{
	return x * y / gcd(x, y);
}

template<class Type>
bool is_prime(Type x)
{
	if (x == 2) return true;
	if (x < 2 || x % 2 == 0) return false;

	for (Type i = 3; i <= sqrt(x); i += 2) {
		if (x % i == 0) return false;
	}
	return true;
}

template<class Type>
vector<bool> eratos(Type n)
{
	vector<bool> isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	for (Type i = 2; i <= n; i++) {
		if (isPrime[i]) {
			Type j = i + i;
			while (j <= n) {
				isPrime[j] = false;
				j = j + i;
			}
		}
	}
	return isPrime;
}

bool binary_search_judge(vector<int> a, int index, int key)
{
	if (key <= a[index]) return true;
	else return false;
}

int binary_search(vector<int> a, int key)
{
	int ng = -1;
	int ok = a.size();
	while (1 < abs(ng - ok)) {
		int mid = (ng + ok) / 2;
		if (binary_search_judge(a, mid, key)) ok = mid;
		else ng = mid;
	}
	return a[ok] == key;
}

double expected_value(double x)
{
	double ans = 0;
	for (int i = 1; i <= x; i++) {
		ans += i * (1.0 / x);
	}
	return ans;
}

int main()
{
	int n, k;
	cin >> n >> k;
	vector<double> p(n);
	for (int i = 0; i < n; i++) cin >> p[i];

	vector<double> s(n + 1);
	for (int i = 0; i < n; i++) {
		s[i + 1] = s[i] + expected_value(p[i]);
	}

	double ans = 0;
	for (int i = 0; i < n - k + 1; i++) {
		double tmp = s[i + k] - s[i];
		ans = max(ans, tmp);
	}
	cout << std::fixed << std::setprecision(15) << ans << endl;
}

Measured memory_bytes: 3328
#include <iostream>

using namespace std;

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

    int N;
    cin >> N;

    if (N < 1000) {
        cout << "ABC" << '\n';
    } else {
        cout << "ABD" << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n);
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

int main()
{
    int n;
    string a, b, c;
    cin>>n>>a>>b>>c;

    int ans = 0;
    REP(i,n) {
        if (a[i] == b[i]) {
            if (a[i] == c[i])
                continue;
            else
                ans++;
        } else if (b[i] == c[i] || a[i] == c[i]) {
            ans++;
        } else {
            ans += 2;
        }
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    private static int n;

    private static void dfs(String s, char mx) {
        if (s.length() == n) {
            System.out.println(s);
            return;
        }
        for (int i = 0; i <= mx - 'a'; i++) {
            if (i == mx - 'a') {
                dfs(s + (char) (i + 'a'), (char) (mx + 1));
            } else {
                dfs(s + (char) (i + 'a'), mx);
            }
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs("", 'a');
    }

}


Measured memory_bytes: 79360
// Problem : B - Homework
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 1e6 + 5;
const ll MOD = 1e9 + 7;

// sprawdz MODULO!
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	ll sum = 0;
	REP(i, m) {
		int a;
		cin >> a;
		sum += a;
	}
	if (sum > n) {
		cout << -1;
	} else cout << n - sum;
	return 0;
}
 


Measured memory_bytes: 3648
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

graph = defaultdict(list)
rinsetsu = [[0] * N for i in range(N)]

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    rinsetsu[a-1][b-1] = 1
    rinsetsu[b-1][a-1] = 1

per = list(permutations([n for n in range(1, N)]))
permu = []
for p in per:
    p = [0] + list(p)
    permu.append(p)
ans = 0
for p in permu:
    cnt = 0
    for i in range(N-1):
        a, b = p[i], p[i+1]
        if rinsetsu[a][b] == 1:
            cnt += 1
    if cnt == N - 1:
        ans += 1
print(ans)
        



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

int main() {
    int N, X;
    int m;
    int min = 1000;
    int sum = 0;

    cin >> N >> X;
    for (int i=0; i<N; ++i) {
      cin >> m;
      sum += m;
      if (min > m) min = m;
    }
    cout << (N + ((X - sum) / min)) << endl;

    return 0;
}

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

int main(){
  int64_t a,b,x,y,z;
  cin >> a >> b >> x;
  if(a!=0)y = (a-1)/x+1;
  else y = 0;
  z = b/x;
  cout << z-y+1 << endl;
  return 0;
}


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

map<int, int> d, t;
set<int> s;

signed main() {

    int n;
    scanf("%d", &n);
    for ( int i = 0; i < n; i++ ) {
        int a;
        scanf("%d", &a);
        d[a]++;
    }
    
    int m;
    scanf("%d", &m);
    for ( int i = 0; i < m; i++ ) {
        int a;
        scanf("%d", &a);
        t[a]++;
        s.insert(a);
    }

    for(auto i = s.begin(); i != s.end(); i++) {
        if ( d[*i] < t[*i] ) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");


    return 0;
}

Measured memory_bytes: 28416
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    #[allow(unused_mut)]
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    n: usize,
    w: [i32; n],
  }
  let mut sum = vec![0; n + 1];
  for (i, &x) in w.iter().enumerate() {
    sum[i+1] = sum[i] + x;
  }
  let mut ans = 1 << 20;
  for i in 1..n {
    ans = cmp::min(ans, (sum[n] - 2 * sum[i]).abs());
  }

  println!("{}", ans);
}


Measured memory_bytes: 4352
import heapq

X, Y, A, B, C = [int(s) for s in input().split()]
p = [(-int(s), 'r') for s in input().split()]
q = [(-int(s), 'g') for s in input().split()]
r = [(-int(s), 'n') for s in input().split()]
h = p + q + r
heapq.heapify(h)
x, y, z = 0, 0, 0
s = 0
while x + y + z < X + Y:
    d, c = heapq.heappop(h)
    if c == 'r':
        if x < X:
            x += 1
            s += -d
    if c == 'g':
        if y < Y:
            y += 1
            s += -d
    if c == 'n':
        z += 1
        s += -d
print(s)

Measured memory_bytes: 42844
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define watch(x) cout<<(#x)<<" is "<<x<<endl;
#define ll long long int
#define pb push_back
#define in insert
#define mp make_pair
#define F first
#define S second
#define N 1000000
#define MOD 1000000007
#define PI acos(-1)
int main()
{
	IOS
	string s,t;
	cin>>s>>t;
	int ind=0;
	int m=s.length(),n=t.length();
	if(m==0||n==0)
	{
		cout<<"";
		return 0;
	}
	int dp[m+1][n+1];
	memset(dp,0,sizeof(dp));
	int i,j;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(s[i-1]==t[j-1]){
			dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			}
			else
			dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
		}
	}
	i=m,j=n;
	string str="";
	while(i>0&&j>0)
	{
		int x=max(dp[i][j-1],dp[i-1][j]);
		if(dp[i][j]>x){
		str=str+s[i-1];
		i--;
		j--;}
		else
		{
			if(dp[i][j-1]>dp[i-1][j])
			j--;
			else
			i--;
		}
	}
	reverse(str.begin(),str.end());
	cout<<str;
}

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


const int INF = 1001001001;

int main() {

    /*
     * 赤色の個数をA個とり緑色の個数をB個、無色をC個取るとすると
     * X+Y = A+B+C ...⓵
     * A <= X ...⓶
     * B <= Y ...⓷
     * が条件
     *
     * １．X個大きい順から取る、Y個大きい順から取る、それ以外のものは消す（これで⓶⓷を常に満たすようにできる）
     * ２．すると、あとはその赤色と緑色と無色のものから好きに大きい順から取る
     * */

    int x, y;
    cin >> x >> y;
    int a, b, c;
    cin >> a >> b >> c;
    vector<int> p(a), q(b), r(c);
    rep(i,a) cin >> p[i];
    rep(i,b) cin >> q[i];
    rep(i,c) cin >> r[i];
    sort(p.rbegin(), p.rend()); // rはリバースでこれで降順になる
    sort(q.rbegin(), q.rend());
    vector<int> d;
    rep(i,x) d.push_back(p[i]);
    rep(i,y) d.push_back(q[i]);
    rep(i,c) d.push_back(r[i]);
    sort(d.rbegin(), d.rend());
    ll ans = 0;
    rep(i,x+y) ans += d[i];
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3572
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int r = sc.nextInt();
            int D = sc.nextInt();
            int i = sc.nextInt();

            long result = calc(r, D, i);

            for (int j = 1; j < 10; j++) {
                result = calc(r, D, result);
            }

        }
    }

    static long calc(int r, int D, long i) {
        long result = r * i - D;
        System.out.println(result);
        return result;
    }

}

Measured memory_bytes: 21588
#include <iostream>
#include <map>
#include <string>

using namespace std;

map<string, int> words;

int main(){
  int N;
  cin >> N;
  string w_prev;
  for (int i=0;i<N;i++) {
    string w;
    cin >> w;
    if (i>0) {
      if (words.find(w) != words.end()) {
	cout << "No" << endl;
	return(0);
      }
      if (w_prev[w_prev.length()-1] != w[0]) {
	cout << "No" << endl;
	return(0);
      }
    }
    words[w] = 1;
    w_prev = w;
  }
  cout << "Yes" << endl;
  return(0);
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b;
  
  c = a * b;
  
  if (c % 2 == 0) {
    cout << "Even" << endl;
  }
  
  else {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5;
bool jay;
int l,r,n,m,opt,x;
int a[N];
char str[N];
int main()
{
	scanf("%s",str+1);
	l=1e6+1; r=1e6;
	n=strlen(str+1);
	for (register int i=1; i<=n; ++i)
	{
		r++;
		a[r]=str[i]-'a';
	}
	int jay=1;
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d",&opt);
		if (opt==1) jay^=1;
		else
		{
			scanf("%d",&x);
			char ch;
			cin>>ch; 
			if (jay)
			{
				if (x==1) l--,a[l]=ch-'a';
				else r++,a[r]=ch-'a';
			}
			else
			{
				if (x==1) r++,a[r]=ch-'a';
				else l--,a[l]=ch-'a';
			}
		}
	}
	if (jay) for (register int i=l; i<=r; ++i) putchar((char)a[i]+'a');
	else for (register int i=r; i>=l; --i) putchar((char)a[i]+'a');
	return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>

int main(void)
{
    int H=0,W=0,i,j;
    for (; ; )
    {
        scanf("%d %d",&H,&W);
        if (H==0&&W==0)
            break;
        for (i=0; i<H; i++)
        {
            for (j=0; j<W; j++)
            {
                if (i==0)
                    printf("#");
                else if (j==0)
                    printf("#");
                else if(i==(H-1))
                    printf("#");
                else if (j==(W-1))
                    printf("#");
                else
                    printf(".");
            }printf("\n");
        }printf("\n");
    }
    return 0;
}

Measured memory_bytes: 572
n = int(raw_input())
d = [100 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
  
def Bread(s):
    for e in range(n):
        if v[s][e] == 1:
            if d[e] > d[s] + 1:
                d[e] = d[s]+1
                Bread(e)
  
for i in range(n):
    G = map(int, raw_input().split())
 
    for j in range(G[1]):
        v[G[0]-1][G[j+2]-1] = 1
 
d[0] = 0
  
for i in range(n):
    Bread(i)
 
for i in range(n):
    if d[i] == 100:
        d[i] = -1
 
for i in range(n):
    print i+1, d[i]

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

int main(){
  string T;
  cin >> T;
  int C=T.size();
  for(int i=0;i<C;i++){
    if(T.at(i)=='?'){
      T.at(i)='D';
    }
    cout << T.at(i);
    if(i==C-1){
      cout << endl;
    }
  }
}

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

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

    A_sorted = sorted(A)
    B_sorted = sorted(B)
    for a, b in zip(A_sorted, B_sorted):
        if a > b:
            print('No')
            exit()
    for i in range(N-1):
        if A_sorted[i+1] <= B_sorted[i]:
            print('Yes')
            exit()

    AB = [(a, b) for a, b in zip(A, B)]
    AB.sort(key=lambda x: x[1])
    A_new = [ab[0] for ab in AB]
    a2i = {a: i for i, a in enumerate(A_new)}
    A_cmp = [0] * N
    for i, a in enumerate(sorted(A_new)):
        A_cmp[a2i[a]] = i
    cnt = 0
    i = 0
    seen = [0] * N
    while True:
        if not seen[i]:
            seen[i] = 1
            cnt += 1
            i = A_cmp[i]
        else:
            break
    if cnt == N:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()


Measured memory_bytes: 89448
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n,m,a[N][N];
bool vis[N][N];
bool judge()
{
    for(int i=1;i<=3;i++)
    {
        bool flag=true;
        for(int j=1;j<=3;j++)
            if(!vis[i][j]) flag=false;
        if(flag) return flag;
    }
    for(int j=1;j<=3;j++)
    {
        bool flag=true;
        for(int i=1;i<=3;i++)
            if(!vis[i][j]) flag=false;
        if(flag) return flag;
    }
    return vis[1][1]&&vis[2][2]&&vis[3][3]||vis[1][3]&&vis[2][2]&&vis[3][1];
}
int main()
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++) scanf("%d",&a[i][j]);
    scanf("%d",&n);
    while(n--)
    {
        int x;scanf("%d",&x);
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
            if(a[i][j]==x) vis[i][j]=true;
    }
    if(judge()) printf("Yes\n");
    else printf("No\n");
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    string T;
    rep(i, S.length()) {
        if(S[i] != 'B') T += S[i];
        else if(!T.empty()) T.pop_back();
    }
    cout << T << endl;


    return 0;
}


Measured memory_bytes: 3624
/*
* @Author: kabbo
* @Date:   2020-05-10 12:08:52
* @Last Modified by:   kabbo
* @Last Modified time: 2020-05-10 12:15:18
*/
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define endl '\n'
#define ull unsigned long long
#define ll long long
const int mod = 1e9 + 7;
using u64 = uint64_t;
using u128 = __uint128_t;
void solve() {
	int n;
	cin >> n;
	vector<int>h(n + 1);
	for (int i(1); i <= n; ++i)
		cin >> h[i];
	int dp[n + 1] = {0};
	for (int i(2); i <= n; ++i) {
		auto ith = abs(h[i] - h[i - 1]) + dp[i - 1];
		auto ith_2 = i > 2 ? abs(h[i] - h[i - 2]) + dp[i - 2] : INT_MAX;
		dp[i] = min(ith, ith_2);
	}
	cout << dp[n] << endl;
}
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	/*int t;
	cin >> t;
	for (int i(1); i <= t; ++i) {*/
	//printf("Case %d: ", i);
	solve();
	//}
#ifndef LOCAL_DEFINE
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray();
        int sum = 0;
        for(char c : a) {
            sum += c - '0';
            sum %= 9;
        }
        System.out.println(sum==0 ? "Yes":"No");


    }



}

Measured memory_bytes: 40704
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    int a[n];
    REP(i,n){
        cin >> a[i];
    }
    int ans = 0;
    REP(i,n){
        if(a[a[i] - 1] == i + 1){
            ans++;
        }
    }
    cout << ans / 2 << endl;
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>

int main(void)
{
  int n;
  int count=0;
  int max=0;

  scanf("%d",&n);
  int ans=n;
  for(int i=1;i<=n;i++)
  {
    int tmp=i;
    //printf("%d\n",tmp);
    for(int j=0;j<i;j++)
    {
      if((tmp/2)!=0&&(tmp%2)==0){
        tmp=tmp/2;
        count++;
      }
      else{
        break;
      }
    }
    if(max<count){
      //printf("%d\n",count);
      max=count;
      ans=i;
    }
    count=0;
  }
  printf("%d\n",ans);
}


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

int main() {
    int N;
    int A[210], cnt[210];

    cin >> N;
    for (int i=0; i<N; ++i) cin >> A[i];

    int res = 1e9;

    for (int i=0; i<N; ++i){
        cnt[i] = 0;
        int x = A[i];
        while (true) {
           if ((x % 2 == 0) and (x != 0)) {
               cnt[i]++;
               x = x / 2;
           }
           else{
               break;
           }
        }
        res = min(res, cnt[i]);
    }

    cout << res << endl;

}


Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector <ll> vll;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define MAX 1000000
#define mod 1000000007
#define all(_) _.begin(), _.end()
#define F first
#define S second
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll n, k, i, j;
    cin >> n >> k;
    vll a(n);
    for(i = 0; i < n; i++)
        cin >> a[i];
    ll dp[2][k + 1], toggle = 0;
    memset(dp, 0, sizeof dp);
    vll psum(k + 1, 0);
    for(i = 0; i <= a[0]; i++)
        dp[toggle][i] = 1;
    for(i = 1; i < n; i++, toggle ^= 1)
    {
        psum[0] = dp[toggle][0];
        for(j = 1; j <= k; j++)
            psum[j] = (psum[j - 1] + dp[toggle][j]) % mod;
        dp[toggle ^ 1][0] = 1;
        for(j = 1; j <= k; j++)
        {
            ll left = max(0ll, j - a[i]);
            ll right = j;
            dp[toggle ^ 1][j] = (psum[right] - (left ? psum[left - 1] : 0) + mod) % mod;
        }
    }
    cout << dp[toggle][k] << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip	;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1<<30;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int dp[110][110];
int main(){
	int n,m;
	while(cin>>m>>n,n+m){
		vector<string>in(n);
		rep(i,n)cin>>in[i];
		queue<pip>q;
		int sx,sy;
		rep(i,110)rep(j,110)dp[i][j]=inf;
		rep(i,n)rep(j,m)if(i==0||j==0||i==n-1||j==m-1){
			if(in[i][j]!='#'){
				q.push(pip(i,pii(j,0)));
				dp[i][j]=0;
			}else{
				q.push(pip(i,pii(j,1)));
				dp[i][j]=1;
			}
		}
		rep(i,n)rep(j,m)if(in[i][j]=='&')sx=i,sy=j;
		while(!q.empty()){
			pip p=q.front();
			q.pop();
			int x=p.first,y=p.second.first,cost=p.second.second;
//			cout<<x<<" "<<y<<" "<<cost<<endl;
			if(dp[x][y]<cost)continue;
			rep(k,4){
				int nx=x+dx[k],ny=y+dy[k];
				if(nx<0||ny<0||nx>=n||ny>=m)continue;
				int ncost=cost+(in[nx][ny]=='#'?1:0);
				if(in[nx][ny]=='#'&&in[x][y]=='#')ncost--;
//				cout<<" "<<nx<<" "<<ny<<" "<<ncost<<endl;
				if(dp[nx][ny]>ncost){
					dp[nx][ny]=ncost;
					q.push(pip(nx,pii(ny,ncost)));					
				}
			}
		}
		cout<<dp[sx][sy]<<endl;
	}
}

Measured memory_bytes: 1312
#coding:utf-8

S = input()

margin = 0
for i, moji in enumerate(S):
    if moji == 'B':
        margin = i
        break

idx_list = []
for i, moji in enumerate(S[margin:]):
    if moji == 'W':
        idx_list.append(i)

q = len(idx_list) - 1
print(sum(idx_list) - int(0.5 * q * (q + 1)))


Measured memory_bytes: 11368
use std::cmp::max;
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let n: usize = s.trim().parse().unwrap();
    let mut a_cnt = 1;
    let mut b_cnt = 1;
    let mut t = 1;

    for _ in 0..n {
        let mut s = String::new();
        stdin().read_line(&mut s).ok();
        let mut itr = s.split_whitespace().map(|e| e.parse::<usize>().unwrap());
        let a = itr.next().unwrap();
        let b = itr.next().unwrap();
        t = max((a_cnt + a - 1) / a, (b_cnt + b - 1) / b);
        a_cnt = a * t;
        b_cnt = b * t;
    }

    println!("{}", (a_cnt + b_cnt));
}


Measured memory_bytes: 4352
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include <list>
#include <utility>
#include <memory>
#include <cstring>
#include <fstream>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <ios> 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int a[100004],b[100004];
ll ans[100004];
int f[100004];
ll num[100004];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
	cin>>n>>m;
	ans[m-1]=1ll*n*(n-1)/2;
	for (int i=1;i<=n;i++) f[i]=i,num[i]=1;
	for (int i=0;i<m;i++) scanf ("%d%d",&a[i],&b[i]);
	for (int i=m-2;i>=0;i--){
		ans[i]=ans[i+1];
		int q=i+1;
		int a1=a[i+1],a2=b[i+1];
		a1=find(a1),a2=find(a2);
		if (a1==a2) continue;
		ans[i]-=num[a1]*num[a2];
		num[a1]+=num[a2];
		f[a2]=a1;
	}
	for (int i=0;i<m;i++) printf ("%lld\n",ans[i]);
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L
const int mxN = 1e9 + 7;


int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int l = 1, r = 1e9;
    int ans = 0;
    while (l <= r) {
        int m = l + (r - l) / 2;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (a[i]-1) / m;
        }
        if (sum > k) {
            l = m + 1;
        }
        else {
            ans = m;
            r = m - 1;
        }
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 3952
#include<stdio.h>

int dx[4]={0,0,1,1},dy[4]={0,1,0,1};
char map[1003][1003],flag[3][3];

bool isflag(int x, int y){
    int nx,ny,i;
    for(i=0; i<4; i++){
        nx = x+dx[i];
        ny = y+dy[i];
        if(map[nx][ny]!=flag[dx[i]][dy[i]]){
            return false;
        }
    }
    return true;
}

int main(void){
    int m,n,ans=0,max=0,i,j,h,a,b,c,d,e,nx,ny;
    char tmp;
    scanf("%d%d",&m,&n);
    for(i=0; i<(n+2); i++){
        map[0][i]='.';
        map[m+1][i]='.';
    }
    for(i=1; i<=m; i++){
        scanf("%s",map[i]);
        for(j=n; j>0; j--){
            map[i][j] = map[i][j-1];
        }
        map[i][0]='.';
        map[i][n+1]='.';
    }
    for(i=0; i<2; i++){
        scanf("%s",flag[i]);
    }
    for(i=1; i<m; i++){
        for(j=1; j<n; j++){
            if(isflag(i,j)){
                ans++;
            }
        }
    }
    for(i=1; i<=m; i++){
        for(j=1; j<=n; j++){
            tmp = map[i][j];
            e = 0;
            //J???????????????
            map[i][j] = 'J';
            d = 0;
            for(h=0; h<4; h++){
                nx = i-dx[h];
                ny = j-dy[h];
                if(isflag(nx,ny)){
                    d++;
                }
            }
            if(map[i][j]==tmp){
                c = d;
            }else{
                a = d;
                e = 1;
            }
            //O???????????????
            map[i][j] = 'O';
            d = 0;
            for(h=0; h<4; h++){
                nx = i-dx[h];
                ny = j-dy[h];
                if(isflag(nx,ny)){
                    d++;
                }
            }
            if(map[i][j]==tmp){
                c = d;
            }else if(e==0){
                a = d;
                e = 1;
            }else{
                b = d;
            }
            //I???????????????
            map[i][j] = 'I';
            d = 0;
            for(h=0; h<4; h++){
                nx = i-dx[h];
                ny = j-dy[h];
                if(isflag(nx,ny)){
                    d++;
                }
            }
            if(map[i][j]==tmp){
                c=d;
            }else{
                b=d;
            }
            //??????
            map[i][j] = tmp;
            c*=-1;
            c+=(a>b)?a:b;
            max = (max>c)?max:c;
        }
    }
    printf("%d\n",ans+max);
    return 0;
}

Measured memory_bytes: 2008
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF (long long)1e17
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int a[n];
  int sum=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  int ans=INF;
  int now=0;
  rep(i,n){
    ans=min(ans,abs((sum-now)-now));
    now+=a[i];
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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 <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

int main() {
    int n;
    cin >> n;
    vector<tuple<ll, ll, int>> v(n), w(n);
    rep(i, n) {
        ll x, y;
        cin >> x >> y;
        v[i] = make_tuple(x, y, i);
        w[i] = make_tuple(y, x, i);
    }
    sort(all(v));
    sort(all(w));
    vector<tuple<ll, int, int>> es;
    rep(_, n - 1) {
        ll a, b, c, d;
        int i, j;
        tie(a, b, i) = v[_];
        tie(c, d, j) = v[_ + 1];
        es.emplace_back(min(abs(a - c), abs(b - d)), i, j);
    }
    rep(_, n - 1) {
        ll a, b, c, d;
        int i, j;
        tie(a, b, i) = w[_];
        tie(c, d, j) = w[_ + 1];
        es.emplace_back(min(abs(a - c), abs(b - d)), i, j);
    }

    sort(all(es));
    ll ans = 0;
    UnionFind uf(n);
    for (auto e : es) {
        int a, b;
        ll c;
        tie(c, a, b) = e;
        if (!uf.find(a, b)) {
            ans += c;
            uf.unite(a, b);
        }
    }
    cout << ans << endl;
}

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

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>

using namespace std;

typedef pair<int,int> Paint;

bool Pairsecond(const Paint& pf,Paint&ps){//sortCompare
  return pf.second < ps.second;
}

#define anyfill(n,s) setw(n) << setfill(s)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define pb push_back
#define MAX 1000000000
#define MOD 1000000007

/*
確認ポイント
cout<< (char)数値 //数値にあった文字に置き換えられる
cout<< (double)int型/(2など)//小数になる
length(),size()に括弧をつけ忘れてないか;
sort()が使える型//vector,string...
YesNo大文字小文字間違えてないか
cout << fixed << 小数計算//正しい小数表記になる(基本6桁)(e記法回避にも使える)
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
sqrt(数値型)でrootが取れる
vector.unique()は隣接した同じ要素を削除するので先にソートをする
*/



int main(){
  long long n;cin>>n;
  long long a[n+1];
  for(int i = 0; n+1 > i; i++){
    cin>>a[i];
  }
  long long b[n];
  for(int i = 0; n > i; i++){
    cin>>b[i];
  }
  long long ans = 0;
  for(int i = 0; n > i; i++){
    if(a[i] >= b[i]){
      ans += b[i];
    }else{
      ans += a[i];
      ans += min(b[i]-a[i],a[i+1]);
      a[i+1] -= min(b[i]-a[i],a[i+1]);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1920
#include<iostream>
#include<algorithm>
#include<functional>
#include<math.h>
 
using namespace std;
 
int main() {
	int N, x, mid;
  long ans = 0;
	long A[200005], B[200005];
 
	cin >> N;
 
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i] = A[i]-(i+1);
 
	}
	sort(B, B+N);
 
 
  mid = B[N/2];
  for (int i = 0; i < N; i++) {
    x = B[i] - mid;
    ans += abs(x);
  }

	cout << ans <<endl;
 
	return 0;
}

Measured memory_bytes: 3328
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
typedef array<LL,3> A;
vector<P> tree[1001];

// powmod p^n%mod
LL powmod(LL p,LL n,LL mod){
	LL q=p%mod;
	LL pow=1;
	while(n){
		if(n&1){
			pow*=q;
			pow%=mod;
		}
		q=q*q;
		q%=mod;
		n/=2;
	}
	return pow;
}
LL f(int s, int p, int e)
{
	for(P t:tree[s]){
		if(t.first==p)continue;
		if(t.first==e){
			return t.second;
		}
		LL v=f(t.first,s,e);
		if(v){
			return max(v,t.second);
		}
	}
	return 0;
}
vector<A> es;
const int MD=1e9+7;
int main() {
	LL N,M,X;
	cin >> N >> M >> X;
	for(int i=0;i<M;i++){
		LL u,v,w;
		cin >> u >> v >> w;
		es.push_back(A{{w,u,v}});
	}
	sort(es.begin(),es.end());
	vector<LL> ds;
	LL sum=0;
	for(auto a:es){
		LL v=f(a[1],0,a[2]);
		if(v==0){
			tree[a[1]].push_back(P(a[2],a[0]));
			tree[a[2]].push_back(P(a[1],a[0]));
			sum+=a[0];
			ds.push_back(0);
		}
		else{
			ds.push_back(a[0]-v);
		}
	}
	LL ls=0;
	LL gt=0;
	LL eq=0;
	for(int d:ds){
		if(d>X-sum){
			gt++;
		}
		else if(d==X-sum){
			eq++;
		}
		else{
			ls++;
		}
	}
	LL ret=1;
	if(eq==0){
		cout << 0 << endl;
		return 0;
	}
	if(ls){
		ret=powmod(2,eq+gt,MD)+MD-powmod(2,gt,MD);
		ret%=MD;
		ret*=2;
		ret%=MD;
	}
	else{
		ret=powmod(2,eq+gt,MD)+2*(MD-powmod(2,gt,MD));
		ret%=MD;
	}
	cout << ret << endl;

	return 0;
}



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

using namespace std;

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

#define pb push_back
#define mp make_pair

string s;
ll n;

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> s;
    n = s.length();
    int cnt[26] = {};
    ll ans = 1;
    for(int i = 0; i < n; i++){
        ans += i;
        ans -= cnt[s[i] - 'a'];
        cnt[s[i] - 'a']++;
    }
    cout << ans << endl;
    return 0;
}


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

// Union-Find木 (経路圧縮あり、ランク無し、サイズあり)
// ref. https://www.slideshare.net/chokudai/union-find-49066733
struct UnionFind {
  vector<int> parent;
  vector<int> size;

  UnionFind(int n) {
    parent.resize(n);
    size.resize(n, 1);
    for (int i = 0; i < n; i++) {
      // parent[i] = i ならば根
      parent.at(i) = i;
    }
  }

  // 木の根を求める
  int root(int x) {
    // 頂点 x が根の場合は根の値を返す
    if (parent.at(x) == x) {
      return x;
    // 頂点 x が根ではない場合は経路圧縮を行いつつ、根の値を返す
    } else {
      // 経路圧縮
      parent.at(x) = root(parent.at(x));
      return parent.at(x);
    }
  }

  // 頂点 x と y が同じ集合に属するか否か
  bool same(int x, int y) {
    return root(x) == root(y);
  }

  // 頂点 x が所属する集合のサイズを求める
  int size_of(int x) {
    return size.at(root(x));
  }

  // 頂点 x と y の属する集合を併合
  void unite(int x, int y) {
    // 2頂点の根を求める
    x = root(x);
    y = root(y);

    // 頂点 x と y が同じ集合に所属している場合は併合する必要がない
    if (x == y) { return; }

    // 要素数が多い方に併合する
    if (size.at(x) > size.at(y)) {
      // 以下の親子関係となる
      // (x == root of x || y == root of y のケースもある)
      //
      // [y] --> [root of y] --+
      //                       |--> [root of x]
      // [x] ------------------+
      //
      parent.at(y) = x;
      size.at(x) += size.at(y);
    } else {
      parent.at(x) = y;
      size.at(y) += size.at(x);
    }
  }
};

int main() {
  int n; // 人数
  cin >> n;
  int m; // 情報の数
  cin >> m;

  UnionFind uf(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--; // 0-indexed
    uf.unite(x, y);
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans = max(ans, uf.size_of(i));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4836
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

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

    ll N;
    cin>>N;

    ll s = 0;
    rep(i, N) s += i;
    cout<<s<<endl;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

#define huge 1000000007

int main(void) {

	long int N = 0, A=0, B = 0,D=0;
	cin >> N >> A >> B;
	int h = 0;
	int hoge = 0;
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		h = i;
		if (h == 10000) {
			hoge = 1;
		}
		else if (h >= 1000) {
			hoge += h / 1000;
			h%= 1000;
			hoge += h / 100;
			h %= 100;
			hoge += h / 10;
			h %= 10;
			hoge += h;
		}
		else if (h >= 100) {
			hoge += h / 100;
			h %= 100;
			hoge += h / 10;
			h %= 10;
			hoge += h;
		}
		else if (h >= 10) {
			hoge += h / 10;
			h %= 10;
			hoge += h;
		}
		else{
			
			hoge += h;
		}

		

		if (A <= hoge && B >= hoge) {
			sum += i;
			//cout << i << hoge << endl;
		}
		hoge = 0;
	}

	cout << sum << endl;
	return 0;


}


Measured memory_bytes: 256