akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int h, a;
    cin >> h >> a;

    int i = 0;
    while (true)
    {
        if (h <= 0)
        {
            break;
        }

        h -= a;
        i++;
    }

    cout << i << endl;
}


Measured memory_bytes: 256
#dp[i]:i番目の足場に達した時のコストの最小値
#dp[i] = min(dp[i-k]+abs(h[i]-h[i-k])) (1<=k<=K)
#このままだとO(NK)で間に合わない?

import numpy as np

N, K = map(int, input().split())

h = np.array(input().split(), dtype=np.int64)
 
dp = np.zeros(N, dtype=np.int64)

for i in range(1, N):
    L = max(0, i-K)
    dp[i] = np.min(dp[L:i] + np.abs(h[i]-h[L:i]))

print(dp[N-1])

Measured memory_bytes: 21968
<?php
fscanf(STDIN, "%s", $S);
$week = array("MON","TUE","WED","THU","FRI","SAT","SUN");
# var_dump($week);
foreach($week as $key => $value){
    if ($value == $S){
        if (6 - $key == 0){
            echo 7;
        }else{
            echo 6 - $key;
        }
    }
}

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

int main()
{
    int n;
    int b, f, r, v;
    int people[5][4][11];
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 11; k++)
            {
                people[i][j][k] = 0;
            }
        }
    }

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> b >> f >> r >> v;
        people[b][f][r] += v;
    }

    for (int i = 1; i < 5; i++)
    {
        for (int j = 1; j < 4; j++)
        {
            for (int k = 1; k < 11; k++)
            {
                cout << " " << people[i][j][k];
            }
            cout << endl;
        }
        if (i < 4)
        {
            cout << "####################" << endl;
        }
    }
}



Measured memory_bytes: 3088
#!/usr/bin/python

if __name__ == "__main__":
	S = raw_input()
	c = ['A','B','C']
	
	while True:
		if len(S) <= 3:
			print "Yes" if S == "ABC" else "No"
			break
		
		T = S.strip().split("ABC")			
		P = ''.join(T)
		
		cnt = 0
		for x in c:
			if x in P:
				cnt += 1
			else:
				S = x.join(T)
		
		if len(T) == 1 or cnt != 2:
			print "No"
			break

Measured memory_bytes: 6480
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::prelude::BufRead;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Write};
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::str::FromStr;

const MOD: usize = 1_000_000_000 + 7;

fn main() {
	let param = read_vector::<usize>();
    let (n, m) = (param[0], param[1]);
    let s1 = read_vector::<usize>();
    let s2 = read_vector::<usize>();
    let mut map1: HashMap<usize, Vec<usize>> = HashMap::new();
    let mut dp = vec![vec![0; m + 1]; n + 1];
    for i in 0..(n + 1) {
        dp[i][0] = 1;
    }
    for i in 0..(m + 1) {
        dp[0][i] = 1;
    }
    for i in 1..(n + 1) {
        for j in 1..(m + 1) {
            dp[i][j] = dp[i][j - 1];
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
            }
            if let Some(vec) = map1.get(&s2[j - 1]) {
                dp[i][j] = (dp[i][j] + vec[j - 1]) % MOD;
            }
        }
        if map1.contains_key(&s1[i - 1]) {
            let vec = map1.get_mut(&s1[i - 1]).unwrap();
            for j in 0..m {
                vec[j] = (vec[j] + dp[i - 1][j]) % MOD;
            }
        } else {
            let mut vec = vec![0; m];
            for j in 0..m {
                vec[j] = dp[i - 1][j];
            }
            map1.insert(s1[i - 1], vec);
        }
    }

    println!("{}", dp[n][m]);
   
}

#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .trim()
        .parse()
        .unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    use std::io::prelude::*;
    let stdin = stdin();
    return stdin
        .lock()
        .lines()
        .map(|line| line
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect())
        .collect();
}

Measured memory_bytes: 71932
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
	int t, p, r;
	while (cin >> t >> p >> r, t, p, r) {
		bool b[60][60] = {};
		int WA[60][60] = {};
		int point[60][2] = {};
		pair<int, pair<int, pair<int, string>>> a[514];
		for (int i = 0; i < r; i++) 
			cin >> a[i].second.first >> a[i].second.second.first >> a[i].first >> a[i].second.second.second;
		sort(a, a + r);
		for (int i = 0; i < r; i++) {
			if (b[a[i].second.first][a[i].second.second.first]);
			else if (a[i].second.second.second[0] == 'W') {
				WA[a[i].second.first][a[i].second.second.first]++;
			}
			else {
				point[a[i].second.first][0]++;
				point[a[i].second.first][1] += WA[a[i].second.first][a[i].second.second.first] * 1200 + a[i].first;
				b[a[i].second.first][a[i].second.second.first] = true;
			}
		}
		pair<int, pair<int, int>> a2[60];
		for (int i = 1; i <= t; i++) {
			a2[i].first = point[i][0];
			a2[i].second.first = point[i][1];
			a2[i].second.second = i;
		}
		for (int i = 1; i < t; i++) {
			for (int j = i + 1; j <= t; j++) {
				if (a2[i].first < a2[j].first)swap(a2[i], a2[j]);
				else if (a2[i].first == a2[j].first) {
					if (a2[i].second.first > a2[j].second.first)swap(a2[i], a2[j]);
					else if (a2[i].second.first == a2[j].second.first) {
						if (a2[i].second.second > a2[j].second.second)swap(a2[i], a2[j]);
					}
				}
			}
		}
		for (int i = 1; i <= t; i++) {
			cout << a2[i].second.second << ' ' << a2[i].first << ' ' << a2[i].second.first << endl;
		}
	}
}

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

#define BUF_SIZE 30

int get_int2(int *a1, int *a2) {
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return -1;
  sscanf(line, "%d %d", a1, a2);
#else
#error
#endif
  return 0;
}

int get_int3(int *a1, int *a2, int *a3) {
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return -1;
  sscanf(line, "%d %d %d", a1, a2, a3);
#else
#error
#endif
  return 0;
}

#define SET_MAX 10000
// create twice in a cut
#define CUTS_MAX 256

struct rect {
    int row;
    int col;
    struct rect *next;
};


static struct rect pool[CUTS_MAX];
static unsigned char pool_pos = 0;

struct rect *create_rect(int row, int col) {
    struct rect *p = &pool[pool_pos++];
    p->row = row; p->col = col;
    // initialize
    p->next = p;
    return p;
}

void push(struct rect *head, struct rect *r) {
    r->next = head->next;
    head->next = r;
}

struct rect *delete(struct rect *head, int move) {
    struct rect *ans = head;
    struct rect *prev;
    while(move--) {
        prev = ans;
        ans = ans->next;
    }
    // delete ans
    prev->next = ans->next;
    ans->next = ans; // initialize
    return ans;
}

int asc(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main(void) {
    int cuts, row, col;
    int i, j;
    static int ans[SET_MAX][CUTS_MAX];
    static int cnt[SET_MAX];
    int ans_idx = 0;
    while(1) {
        get_int3(&cuts, &col, &row);
        if(cuts+col+row==0) break;
        cnt[ans_idx] = cuts+1;
        struct rect *head = create_rect(-1, -1);
        struct rect *r = create_rect(row, col);
        push(head, r);
        // delete -> push -> push
        for(i = 1; i <= cuts; i++) {
            int idx, s;
            // 1-indexed
            get_int2(&idx, &s);
            struct rect *r = delete(head, i+1-idx);
            int half = (r->row + r->col);
            struct rect *small, *large;
            // split
            s %= half;
#ifdef DEBUG
            printf("length %d s: %d\n", half*2, s);
#endif
            if(s >= 0 && s < r->col) {
                int sm = r->col > 2*s ? s : r->col - s;
                // vertical split
                small = create_rect(r->row, sm);
                large = create_rect(r->row, r->col - sm);
            } else {
                // horizontal split
                s -= r->col;
                int sm = r->row > 2*s ? s : r->row - s;
                small = create_rect(sm, r->col);
                large = create_rect(r->row - sm, r->col);
            }
            // push smaller one -> larger one
            push(head, small); push(head, large);
        }
        // pack reverse order.
        struct rect *elem;
        for(elem = head->next, i=0; elem != head; elem = elem->next, i++) {
            ans[ans_idx][i] = elem->row * elem->col;
        }
        ans_idx++;
    }

    // presentation
    for(i = 0; i < ans_idx; i++) {
        int num = cnt[i];
        qsort(ans[i], num, sizeof(int), asc);
        for(j = 0; j < num; j++) {
            printf("%d%c", ans[i][j], j == num-1 ? '\n' : ' ');
        }
    }
    return 0;
}



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

int main() {
    ll n; cin >> n;
    vector<ll> a(n+1); REP(i, n+1) cin >> a[i];
    vector<ll> b(n); REP(i, n) cin >> b[i];

    ll ans = 0;
    REP(i, n) {
        ll tmp = min(a[i], b[i]);
        b[i] -= tmp; ans += tmp;
        ll tmp2 = min(a[i+1], b[i]);
        a[i+1] -= tmp2; ans += tmp2;
    }

    cout << ans << endl;

    return 0;
}

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

int main() {
    long long N, C;
    cin >> N >> C;
    vector<vector<long long>> X(2, vector<long long>(N));
    vector<vector<long long>> V(2, vector<long long>(N));
    vector<vector<long long>> sum(2, vector<long long>(N + 1));
    vector<vector<long long>> S(2, vector<long long>(N + 1));
    rep(i, 0, N) {
        cin >> X[0][i] >> V[0][i];
        X[1][N - i - 1] = C - X[0][i];
        V[1][N - i - 1] = V[0][i];
    }
    rep(i, 0, 2) rep(j, 0, N) {
        sum[i][j + 1] = sum[i][j] + V[i][j];
        S[i][j + 1] = S[i][j] + V[i][j];
    }
    rep(i, 0, 2) rep(j, 0, N) {
        sum[i][j + 1] -= X[i][j];
        S[i][j + 1] -= 2 * X[i][j];
    }
    rep(i, 0, 2) rep(j, 0, N) {
        S[i][j + 1] = max(S[i][j + 1], S[i][j]);
    }
    long long ans = 0;
    rep(d, 0, 2) rep(i, 0, N + 1) {
        ans = max(ans, sum[d][i] + S[d ^ 1][N - i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8048
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
using namespace std;
typedef pair<ll,ll> pll;
ll n , p;
vector< ll > divs;
const ll mod = 1e16 + 3;
ll ME(ll x,ll nn,ll M)
{
    ll result=1;
    while(nn>0)
    {
        if(nn % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        nn=nn/2;
    }
    return result;
}
ll mups(ll x)
{
        return ME(x , n, mod);
}
bool check(ll x)
{
        ll P = p;
        for(ll i=0;i<n;i++) {
                if(P%x != 0) return false;
                P = P/x;
        }
        return true;
}
int main()
{
        cin >> n >> p;
        if(p==1){
                cout << "1\n"; return 0;
        }
        if(n==1){
                cout << p << endl; return 0;
        }
        if(n >= 42) {
                cout << "1\n"; return 0;
        }
        for(ll i=1;i*i <= p;i++) {
                if(p%i == 0) {
                        divs.pb(i);
                        if(i*i != p) divs.pb(n/i);
                }
        }
        sort(divs.begin(), divs.end());
        while(divs.size() > 0) {
                ll u = divs.back();
                if(check(u)) {
                        cout << u << endl; return 0;
                }
                divs.pop_back();
        }
        cout << "1\n";

        return 0;
}


Measured memory_bytes: 256
N,Q=map(int, input().split())
s=input()
S=len(s)
A=[]
for i in range(Q):
  x,y=input().split()
  A.append((x,y))
  
if N==1:
  for x,y in A:
    if s[0]==x:
      print(0)
      exit()
  print(1)
  exit()
  
def L(d):
  for x,y in A:
    if s[d]==x and y=='L':
      d-=1    
    if s[d]==x and y=='R':
      d+=1
    if d<0:
      return False
    elif d==S:
      d-=1
  return True

ok,ng=S,-1
mid=(ok+ng)//2
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if L(mid):
    ok=mid
  else:
    ng=mid
p=ok
if ok==S:
  print(0)
  exit()

def R(d):
  for x,y in A:
    if s[d]==x and y=='L':
      d-=1    
    if s[d]==x and y=='R':
      d+=1
    if d>=S:
      return False
    elif d<0:
      d+=1
  return True

ok,ng=-1,S
mid=(ok+ng)//2
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if R(mid):
    ok=mid
  else:
    ng=mid
q=ok

print(q-p+1)

Measured memory_bytes: 118136
#include<bits/stdc++.h> 
using namespace std; 
//python interactive_runner.py python3 local_testing_tool.py 0 -- ./Code
 
#define x first
#define y second
#define rep(i, a,b) for(int i = int(a); i < int(b); ++i)
#define forn(i,b) for(int i = 0; i < int(b); ++i)
typedef pair<int, int> pii;
int H,W;
const int MAXH = 1000+6;
char grid[MAXH][MAXH];
void solve(){
	
	cin>>H>>W;
	queue<pair<int,int> > q;
	vector<vector<int> > dis(H,vector<int> (W,0));
	vector<vector<int> > vis(H,vector<int> (W,0));
	forn(i,H){
		forn(j,W){
			cin>>grid[i][j];
			if(grid[i][j]=='#'){
				q.push({i,j});
				vis[i][j] = 1;
			} 
		}
	}
	
	int d_x[4] = {-1,1,0,0};
	int d_y[4] = {0,0,-1,1};
	pair<int,int> current;
	int maxdis = 0;
	while(!q.empty()){
		current = q.front();
		q.pop();
		forn(j,4){
			int n_x = current.x + d_x[j];
			int n_y = current.y + d_y[j];
			if(n_x>=0 && n_x<H && n_y>=0 && n_y< W && vis[n_x][n_y]==0){
				vis[n_x][n_y] = 1;
				dis[n_x][n_y] = dis[current.x][current.y]+1;
				maxdis = max(maxdis,dis[n_x][n_y]);
				q.push({n_x,n_y});
				
			}
		}
	}
	cout<<maxdis<<'\n';
}
int main(){
	solve();
	return 0;
}

Measured memory_bytes: 17296
package main

import "fmt"

func main() {
	var weather string
	fmt.Scan(&weather)

	if weather == "Sunny" {
		fmt.Println("Cloudy")
	} else if weather == "Cloudy" {
		fmt.Println("Rainy")
	} else if weather == "Rainy" {
		fmt.Println("Sunny")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<pair<string, int>> l(n);
  REP(i, n) {
    string s;
    int t;
    cin >> s >> t;
    l[i] = make_pair(s, t);
  }

  string t;
  cin >> t;
  bool flag = false;
  int ans = 0;
  REP(i, n) {
    if (flag) {
      ans += l[i].second;
    }
    if (t == l[i].first) {
      flag++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
awk 'BEGIN{getline n;for(i=1;i<=n;i++)getline a[i];getline m;for(i=1;i<=m;i++)getline b[i];for(i=1;i<=n;i++){c=0;for(j=1;j<=n;j++){if(a[i]==a[j])c++}for(j=1;j<=m;j++){if(a[i]==b[j])c--}ans=c>ans?c:ans}print ans?ans:"0"}'

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

namespace atCocderCs
{
    class Program
    {
        static void Main(string[] args)
        {
            var AB = Console.ReadLine().Split(' ').Select((a) => (int.Parse(a))).ToArray();
            var Sarr = Console.ReadLine().Split('-');
            bool res = false;
            if(Sarr.Length == 2)
            {
                if(Sarr[0].Length == AB[0] && Sarr[1].Length == AB[1])
                {
                    res = true;
                }
            }

            Console.WriteLine(res ? "Yes" : "No");
        }
    }
}


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

int main(){
	int n;
	while(cin >>n){
		if(n == 0) break;
		int mato[200][2], i, m;
		bool dp[200][200] = {false};
		for(i = 0; i < n; i++){
			cin >>mato[i][0] >>mato[i][1];
		}
		cin >>m;
		for(; i < (m + n); i++){
			cin >>mato[i][0] >>mato[i][1];
		}
		for(int j = 0; j < (n + m); j++){
			dp[0][j] = true;
		}
		for(int j = 1; j < (n + m); j++){
			for(int k = 0; k < (n + m); k++){
				if(dp[j - 1][k] == true){
					for(int l = 0; l < (n + m); l++){
						if(mato[l][0] > mato[k][0] && mato[l][1] > mato[k][1]){
							dp[j][l] = true;
						}
					}
				}
			}
		}
		
		/*for(int j = 0; j < (n + m); j++){
			cout <<j + 1 <<" : ";
			for(int k = 0; k < (n + m); k++){
				cout <<dp[j][k] <<" ";
			}
			cout <<endl;
		}*/
		int ans;
		bool flag = false;
		for(ans = (n + m - 1); ans >= 0; ans--){
			for(int k = 0; k < (n + m); k++){
				if(dp[ans][k] == true){
					flag = true;
					break;
				}
			}
			if(flag == true) break;
		}
		cout <<ans + 1 <<endl;
	}
	return 0;
}

Measured memory_bytes: 0
h, w, k = map(int, input().split())
k -= 1
MOD = 10 ** 9 + 7

valid_connections = []
for i in range(2 ** (w - 1)):
    if '11' not in bin(i):
        valid_connections.append(i)

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

for i in range(h):
    for j in range(w):
        for connection in valid_connections:
            if connection & (1 << j):
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= MOD
            elif connection & (1 << max(j - 1, 0)):
                dp[i + 1][j - 1] += dp[i][j]
                dp[i + 1][j - 1] %= MOD
            else:
                dp[i + 1][j] += dp[i][j]
                dp[i + 1][j] %= MOD

print(dp[h][k])

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

typedef long long i64;

int n;

i64 c;
i64 k;
i64 t[100010];

#define rep(i,s,e) for(int i = (s);i <= (e);i++)

i64 t_s[100010];
int main()
{
	cin >> n >> c >> k;
	rep(i,1,n) cin >> t[i];

	sort(t + 1,t + n + 1);

	int l = 1;
	int r = 1;
	int sum = 0;
	int result = 0;
	for(;r <= n;r++)
	{
		sum++;
		if(t[r] - t[l] > k)
		{
			result++;
			sum = 1;
			l = r;
		}
		if(sum == c)
		{
          sum =  0;
			result++;
			l = r + 1;
		}
	}

	if(sum != 0)
	{
		result++;
	}

	cout << result << endl;
	return 0;
}
	

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

int main() {
  int n;
  ll a_sum = 0;
  cin >> n;
  vector<ll> a(n);
  vector<ll> b(n);
  rep(i,n) {
    cin >> a[i];
    a_sum += a[i];
  }
  rep(i,n) {
    if(i == 0){
      for(int j = i + 1; j < n; j += 2) {
        a_sum -= 2 * a[j];
      }
      b[0] = a_sum;
    }
    if(i < n -1) {
      b[i + 1] = 2 * a[i] - b[i];
    }
    cout << b[i];
    if(i < n - 1) {
      cout << " ";
    }
  }
  cout << endl;
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
string side[4],Longitudinal[5];
int mox[2][2]={{1,-1},{0,-1}},moy[2][2]={{-1,1},{-1,0}};
char str[5]="URDL";
void serch(int x,int y,int then)
{
    if(then==-1)then=3;
    if(!x&&!y){
        cout<<endl;
        exit(0);
    }
    for(int i=0;i<4;i++){
        int now=(then+i)%4,ka=now/2;
        if(!(now%2)&&y+moy[0][ka]<5&&y+moy[0][ka]>-1&&side[y+moy[1][ka]][x]=='1'){
            cout<<str[now];
            serch(x,y+moy[0][ka],now-1);
        }
        if(now%2&&x+mox[0][ka]<5&&x+mox[0][now/2]>-1&&Longitudinal[y][x+mox[1][ka]]=='1'){
            cout<<str[now];
            serch(x+mox[0][ka],y,now-1);
        }
    }
}
int main()
{
    for(int i=0;i<4;i++)cin>>Longitudinal[i]>>side[i];
    cin>>Longitudinal[4];
    cout<<"R";
    serch(1,0,0);
}

Measured memory_bytes: 3100
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <queue>
#include <vector>
#define maxn 20000
#define oo 1000000000
#define clearAll(a) memset(a,0,sizeof(a))
#define sq(a) ((a)*(a))

using namespace std;

typedef long long ll;

int n,m;
int x[maxn],y[maxn];
struct edge
{
	int x,y;
	ll w;
	edge() {}
	edge(int x,int y,ll w) : x(x),y(y),w(w) {}
};
vector<edge> v;

int set[maxn];

int find(int x)
{
	return set[x]==x?x:set[x]=find(set[x]);
}

bool cmp(edge a,edge b)
{
	return a.w>b.w;
}

int main()
{
   // freopen("C:\\Users\\py\\Desktop\\input.txt","r",stdin);
    //freopen("C:\\Users\\py\\Desktop\\output.txt","w",stdout);
    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)
    	scanf("%d%d",x+i,y+i);

    int p1,p2;
    double tot = 0;
    for (int i=1;i<=m;i++)
    {
    	scanf("%d%d",&p1,&p2);
    	v.push_back(edge(p1,p2,sq((ll)x[p1]-x[p2])+sq((ll)y[p1]-y[p2])));
    	tot += sqrt(v[i-1].w);
    }


    for (int i=1;i<=n;i++)
    	set[i]=i;

    sort(v.begin(),v.end(),cmp);


    for (int i=0;i<m;i++)
    {
    	int xx = find(v[i].x);
    	int yy = find(v[i].y);
    	if (xx!=yy)
    	{
    		tot-=sqrt(v[i].w);
    		set[xx]=yy;
    	}
    }	

    printf("%.8f\n",tot);
    return 0;
}

Measured memory_bytes: 1872
//In the name pf God
#include<bits/stdc++.h>
using namespace std;
int main()
{long long int n,m,sum=0;
 cin>>n>>m;
 long long int a[m];
 for(int i=0;i<m;i++)
    cin>>a[i];
 for(int i=0;i<m;i++)
   sum+=a[i];
 if(sum>n)
   cout<<"-1";
 else
   cout<<(n-sum);
}

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

#define rep(i, s, n) for(int i = s; i < n; ++i)
#define rrep(i, n) for(int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n;
    cin >> n;
    cout << n * n * n << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out,false);
        int h = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] spell = new int[n][2];
        for(int i = 0; i < n; i++) {
            spell[i][0] = scanner.nextInt();
            spell[i][1] = scanner.nextInt();
        }
        int max = 30_000;
        int[] dp = new int[max];
        Arrays.fill(dp, Integer.MAX_VALUE/3);
        dp[0] = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < max - spell[i][0]; j++) {
                dp[j + spell[i][0]] = Math.min(dp[j + spell[i][0]], dp[j] + spell[i][1]);
            }
        }
        int best= Integer.MAX_VALUE;
        for(int i = h; i < dp.length; i++) {
            best = Math.min(best, dp[i]);
        }
        out.println(best);
        out.flush();
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <time.h>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) (min(a,b) <= (x) && (x) <= max(a,b)) //hei
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007LL
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pll Dir[4] = {
	{ -1 ,0 },{ 0 , 1 },{ 1 ,0 },{ 0 ,-1 }
};

//[a, b)
#define Getsum(ar, a,b) (ar[b] - ar[a])
#define INF 10000000000000000LL
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)

struct Edge {
	int from, to;
	ll w;
	bool operator<(const Edge& rhs) const {
		return MP(w, MP(from, to)) < MP(rhs.w, MP(rhs.from, rhs.to));
	}

};
typedef vector<vector<Edge>> Graph;

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


signed main(void) {
	string s;

	cin >> s;

	ll ans = 0, cur = 0;

	REP(i, s.length()) {
		if (s[i] == '>') {
			ans -= cur;
			ll cou = 0;
			for (int j = i; j < s.length(); j++) {
				if (s[j] != '>') break;
				cou++;
			}

			ans += max(cur,cou);
			ans += (cou - 1 + 0) * (cou) / 2;
			i += cou - 1;
			cur = 0;
		}
		else if (s[i] == '<') {
			cur++;
		}
		ans += cur;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 900
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

signed main() {
	int n; scanf("%d", &n);
	int Min = INT_MAX, Max = 0;
	rep(i, n) {
		int a; scanf("%d", &a);
		Min = min(Min, a);
		Max = max(Max, a);
	}
	printf("%d\n", Max - Min);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	set <int> s;
	int n,a;
	cin>>n;
	while(n--)
	{
		cin>>a;
		if(s.count(a)==0)
		s.insert(a);
		else
		s.erase(a);
	}
	cout<<s.size()<<endl;
	return 0;
}



Measured memory_bytes: 4864
use input::Input;

fn main() {
    let mut input = Input::default();

    let h1: u32 = input.parse();
    let m1: u32 = input.parse();
    let h2: u32 = input.parse();
    let m2: u32 = input.parse();
    let k: u32 = input.parse();

    let x = (h2 * 60 + m2) - (h1 * 60 + m1) - k;
    println!("{}", x);
}

#[allow(dead_code)]
pub mod input {
    #[derive(Default)]
    pub struct Input(Vec<String>);

    impl Input {
        pub fn read_line(&mut self) -> String {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).ok().expect("read error");
            s
        }
        pub fn parse<T: std::str::FromStr>(&mut self) -> T {
            let x = if let Some(x) = self.0.pop() {
                x
            } else {
                let s = self.read_line();
                self.0 = s.split_whitespace().map(String::from).rev().collect();
                self.0.pop().expect("reached EOF")
            };
            x.parse().ok().expect("parse error")
        }
    }
}


Measured memory_bytes: 2140
#include <cstdio>
#include <cctype>
#include <algorithm>
#define int long long

int n, m;
int a[100010], fs[100010];
int l = 0, r = 200010, ans, cnt, res;

int read() {
    int ret, f = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * f;
}

void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

signed main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    std::sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) fs[i] = fs[i - 1] + a[i];
    while(l <= r) {
        int mid = (l + r) >> 1;
        cnt = res = 0;
        for(int i = 1; i <= n; ++i) {
            int pos = std::lower_bound(a + 1, a + n + 1, mid - a[i]) - a;
            res += fs[n] - fs[pos - 1] + a[i] * (n - pos + 1); 
            cnt += n - pos + 1;
        }
        if(cnt >= m) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    print(res - ans * (cnt - m));
    return 0;
}

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

using namespace std;

typedef long long ll;

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

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

int main(void) {
    ll T1, T2, A1, A2, B1, B2;
    cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;

    A1 *= T1;
    A2 *= T2;
    B1 *= T1;
    B2 *= T2;

    if (B1 < A1) {
        swap(A1, B1);
        swap(A2, B2);
    }

    if (A1 + A2 < B1 + B2) {
        cout << "0" << endl;
    } else if (A1 + A2 == B1 + B2) {
        cout << "infinity" << endl;
    } else {
        ll a = (A1 + A2) - (B1 + B2);
        ll b = (B1 - A1) / a;
        if (((B1 - A1) % a) == 0) {
            cout << b * 2 << endl;
        } else {
            cout << b * 2 + 1 << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;

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

	string s;
	cin >> s;
	string ans = "";
	for (int i = 0; i < s.length(); i += 2) {
		ans += s[i];
	}
	cout << ans << endl;
	return 0;
}


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

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

  int cnt_tot = 0;
  int cnt_foreign = 0;

  rep(i,n) {
    if(s[i] == 'a'){
      if(cnt_tot < a+b) {cout << "Yes" << endl; cnt_tot++;}
      else cout << "No" << endl;
    }
    else if(s[i] == 'b'){
      if(cnt_tot < a+b && cnt_foreign+1 <= b) {
        cout << "Yes" << endl;
        cnt_tot++;
        //cnt_foreign++;
      }
      else {cout << "No" << endl;}
      cnt_foreign++;
    }
    else {
      cout << "No" << endl;
      //cnt_tot++;
    }
  }
  
}


Measured memory_bytes: 3732
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[105]={},n,k,ans;
int main()
{
	scanf("%d%d",&n,&k);
	ans=n;
	for(int i=1,x,m;i<=k;i++)
		{
			scanf("%d",&m);
			for(int j=1;j<=m;j++)
				{
					scanf("%d",&x);
					if(a[x]==0)
						{
							ans--;
							a[x]=1;
						}
				}
		}
	printf("%d\n",ans);
	return 0;
}


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

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

    vector<int> v(n);
    vector<int> c(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    for(int i = 0; i < n; i++){
        cin >> c[i];
    }
    
    
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(v[i]-c[i] > 0){
            ans += v[i] - c[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = G;
		int N = I[0], C = I[1];
		var cost = new int[C, C];
		for (var i = 0; i < C; i++)
		{
			I = G;
			for (var j = 0; j < C; j++) cost[i, j] = I[j];
		}
		var map = new int[N, N];
		for (var i = 0; i < N; i++)
		{
			I = G;
			for (var j = 0; j < N; j++) map[i, j] = I[j] - 1;
		}
		var ans = N * N * 1001;
		var c2 = new int[3, C];
		for (var i = 0; i < N; i++) for (var j = 0; j < N; j++) for (var c = 0; c < C; c++) c2[(i + j) % 3, c] += cost[map[i, j], c];
		for (var p = 0; p < C; p++)
			for (var q = 0; q < C; q++)
				for (var r = 0; r < C; r++)
					if (p != q && q != r && r != p) ans = Min(ans, c2[0, p] + c2[1, q] + c2[2, r]);
		WriteLine(ans);
	}
}


Measured memory_bytes: 18144
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <tuple>
#include <cassert>
#include <exception>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
static const int INF = 1e+9+7;
ll n,m,l;
string s,t;
int d[200010],dp[1010][1010];
double w[1000],v[1000];
double box[200010];
char field[200][200];

int main(){
  cin >> n >> m >> l;
  vi vec;
  if(m - n <= l){
    lep(i,n,m)print(i);
  }else{
    rep(i,n,n+l)vec.pb(i);
    lep(i,m-l+1,m)vec.pb(i);
    rep(i,1,vec.sz){
      if(vec[i-1] == vec[i]){
        i--;
        vec.erase(vec.begin() + i);
      }
    }
    rep(i,0,vec.sz)print(vec[i]);
  }
  return 0;
}

Measured memory_bytes: 256
N = int(input())
mod = 10**9 + 7

def is_valid(i, j, k, new):
    if (j, k, new) == (0, 1, 2) or (j, k, new) == (0, 2, 1) or (j, k, new) == (2, 0, 1):
        return False
    elif (i, j, k, new) == (0, 2, 2, 1) or (i, j, k, new) == (0, 1, 2, 1) or (i, j, k, new) == (0, 3, 2, 1):
        return False
    elif (i, j, k, new) == (0, 2, 0, 1) or (i, j, k, new) == (0, 2, 2, 1) or (i, j, k, new) == (0, 2, 3, 1):
        return False
    else:
        return True

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
for n in range(3, N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for new in range(4):
                    if n ==3 and (i,j,k)!=(0,1,2) and (i,j,k)!=(1,2,1) and (i,j,k)!=(2,0,1):
                        dp[n][i][j][k]=1
                    elif is_valid(i, j, k, new):
                        dp[n][j][k][new] += dp[n-1][i][j][k]
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)

Measured memory_bytes: 3444
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=304;

int dir[]={-4,4,-1,1};   //上下左右
map<string,int>table;
void bfs(string st)
{
    queue<string>q;
    table[st]=1;    //起始状态
    q.push(st);
    while(!q.empty())
    {
        st=q.front(); q.pop();
        int num=st.find('0');
        for(int i=0;i<4;i++)
        {
            int tn=num+dir[i];
            if(tn<0 || tn>7 || (num==3 && dir[i]==1) || (num==4 && dir[i]==-1))
                continue;
            string tp=st;
            swap(tp[num],tp[num+dir[i]]);
            if(!table[tp])
            {
                q.push(tp);
                table[tp]=table[st]+1;
            }
        }
    }
}


int main()
{
    int num;
    string st="01234567";
    bfs(st);
   while(~scanf("%d",&num))
   {
       st[0]=num+'0';
   
    for(int i=1;i<8;i++)
    {
        scanf("%d",&num);
        st[i]=num+'0';
    }
    printf("%d\n",table[st]-1);
   }
}


Measured memory_bytes: 5560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int a, b, c, d;
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  
  if(a + b > c + d) {
    cout << "Left" << endl;
  }
  else if(a + b < c + d) {
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
} 

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main {
    
    //long[0] = number of ways this node is white
    //long[1] = number of ways this node is black
    static long[] dfs(HashMap<Integer, ArrayList<Integer>> gh, int node, int parent) {
        long white = 1;
        long black = 1;
        // System.out.println("calling for " + node + " p " + parent);
        for(int v : gh.get(node)) {
            if(v != parent) {
                long[] res = dfs(gh, v, node);
                white = (white*(res[0]+res[1]))%MOD;
                black = (black* res[0])%MOD;
            }
        }
        long[] ret = new long[]{white, black};
        // System.out.println("for " + node + " p " + parent + " = " + Arrays.toString(ret));
        return ret;
    }
    static long MOD = 1000*1000*1000 + 7;
    public static void main(String args[]) {
        int n = 0;
        HashMap<Integer, ArrayList<Integer>> gh = new HashMap();
        try (Scanner scanner = new Scanner(System.in)) {
            n = scanner.nextInt();
            for(int i = 0; i < n - 1 ;i++) {
                final int v1 = scanner.nextInt();
                final int v2 = scanner.nextInt();
                gh.compute(v1, (k, v) -> {
                   if(v == null)
                        v = new ArrayList();
                    v.add(v2);
                    return v;
                });
                
                gh.compute(v2, (k, v) -> {
                  if(v == null)
                        v = new ArrayList();
                    v.add(v1);
                    return v;
                });
            }
        }
        if(gh.size() == 0){
            System.out.println(2);
            return;
        }
        long[] ret = dfs(gh, 1, -1);
        System.out.println((ret[0] + ret[1])%MOD);
    }
    
}

Measured memory_bytes: 127620
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	int n;
	vector<int> vec;
	cin >> n;
	int m = 1;
	double a[10], b[10];
	double co = 0;
	for (int i = 0; i < n; i++) {
		vec.push_back(i);
		m *= i + 1;
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < m; i++) {
		for (int i = 1; i < n; i++) {
			double x = a[vec[i - 1]] - a[vec[i]];
			double y = b[vec[i - 1]] - b[vec[i]];
			x *= x;
			y *= y;
			co += sqrt(x + y);
		}
		next_permutation(vec.begin(), vec.end());
	}
	cout << fixed << setprecision(16) << co / m << endl;
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.List
import Data.Char
strToInt s = (read :: String -> Int) s
strToInteger s = (read :: String -> Integer) s
strToDouble s = (read :: String -> Double) s

main :: IO ()
main = do
    -- スペース区切り整数の入力
    [h, w] <- map strToInt . words <$> getLine
    -- 出力
    putStrLn . show $ min (solve h w) (solve w h)

solve :: Int -> Int -> Int
solve h w = if ((h `mod` 3) == 0 || (w `mod` 3) == 0)
            then 0
            else min ver hor where
                ver = minimum [let chocor = map (* w) [k, (h-k) `div` 2, (h-k) - (h-k) `div` 2] in (maximum chocor - minimum chocor) | k <- [1..h-1]]
                hor = minimum [let chocos = [k * w, (h-k) * (w `div` 2), (h-k) * (w - w `div` 2)] in (maximum chocos - minimum chocos) | k <- [1..h-1]]


Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n;
    cin >> n;
    
    vector<pii> v(n);
    rep(i, n) { cin >> v[i].F; v[i].S = i; }
    
    sort(all(v), greater<pii>());
    
    // multiset<int> s;
    set<int> s;
    s.insert(-1);
    s.insert(n);
    /*
    s.insert(-1);
    s.insert(n);
    */
    s.insert(-2);
    s.insert(n + 1);
    
    ll ans = 0;
    rep(i, n) {
        auto it = s.upper_bound(v[i].S);
        auto it2 = it;
        ++it2;
        auto it3 = it;
        --it3;
        auto it4 = it3;
        --it4;
        /*
        if (*it3 != -1) ans += v[i].F * (*it - v[i].S) * (v[i].S - *it4);
        if (*it != n) ans += v[i].F * (*it2 - v[i].S) * (v[i].S - *it3);
        s.insert(v[i].S);
        
        
        {
            cout << endl << *it << " " << *it2 << " " << *it3 << " " << *it4 << endl;
            cout << (*it - v[i].S) << " " << (v[i].S - *it4) << " " << (*it2 - v[i].S) << " " << (v[i].S - *it3) << endl;
            cout << ans << endl;
        }
        */
        // cout << endl << *it << " " << *it2 << " " << *it3 << " " << *it4 << endl;
       
        if (*it3 != -1) ans += (ll)v[i].F * (*it - v[i].S) * (*it3 - *it4);
        if (*it != n) ans += (ll)v[i].F * (*it2 - *it) * (v[i].S - *it3);
        
        s.insert(v[i].S);
    }
    // rep3(i, 1, n) ans -= v[i].F; // 最初以外要素数1countしてた
    cout << ans << endl;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    cin>>n>>x;
    vector<int> l(n);
    for(int i=0;i<n;++i)cin>>l[i];
    int now = 0;
    int cnt = 1;
    while(cnt <= n)
    {
        if(now + l[cnt-1] <= x)
        {
            now += l[cnt-1];
            cnt++;
        }else
            break;
    }
    cout<<cnt<<endl;
}

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

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(ull i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define iter(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define riter(i,c) for(auto i=(c).rbegin(); i!=(c).rend(); ++i)
const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;
namespace std {
    template<typename T>ostream&operator<<(ostream&os, vector<T>const&v){
        iter(it,v) os<<*it<<(it+1==v.end()?"":",");
        return os;
    }
    template<typename T, typename U>ostream&operator<<(ostream&os,const pair<T,U>&p){
        return os << "[" << p.dirst << "," << p.second << "]";
    }
}

void visit(const vvi &g, int v, vvi& scc,
           stack<int> &S, vector<bool> &inS,
           vector<int> &low, vector<int> &num, int& time) {
    low[v] = num[v] = ++time;
    S.push(v); inS[v] = true;
    iter(e, g[v]) {
        int w = *e;
        if (num[w] == 0) {
            visit(g, w, scc, S, inS, low, num, time);
            low[v] = min(low[v], low[w]);
        } else if (inS[w])
            low[v] = min(low[v], num[w]);
    }
    if (low[v] == num[v]){
        scc.push_back(vi());
        while (1) {
            int w = S.top(); S.pop(); inS[w] = false;
            scc.back().push_back(w);
            if (v == w) break;
        }
    }
}
 
void scc(vvi const& g, vvi& res) {
    int const n = g.size();
    vi num(n), low(n);
    stack<int> S;
    vector<bool> inS(n);
    int time = 0;
    rep(u,n)if(num[u]==0) visit(g, u, res, S, inS, low, num, time);
}
 
bool f(string const& a, string const& b){
    if(a.size()!=b.size()) return false;
    bool res=true;
    rep(i,a.size()){
        if(a[i]=='*') continue;
        if(a[i]!=b[i]){
            res=false;
            break;
        }
    }
    return res;
}
 
int main(){
    int n,m;
    while(cin>>n>>m &&  n|m){
        vs s(n);
        vi a(n);
        rep(i,n) cin >> s[i] >> a[i];
        ull ans = 0;

        rep(i,m){
            string t;
            cin >> t;
            rep(j,n){
                if(f(s[j],t)){
                    ans+=a[j]; break;
                }
            }
        }

        cout << ans << endl;
    }
}

Measured memory_bytes: 1204
h,w = map(int,input().split())
h_a = h % 2
w_a = w % 2
h_b = h // 2 
w_b = w // 2 
if(h == 1 or w == 1):
  print(1)

elif((h_a == 0) & (w_a == 0)):
  print(h_b * w)
elif((h_a == 1) & (w_a == 0)):
  print(w_b * h)
elif((h_a == 0) & (w_a == 1)):
  print(h_b * w)
elif((h_a == 1) & (w_a == 1)):
  print((h_b + 1) * (w_b + 1) + h_b * w_b)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = sum(b)
for i in range(1, n):
    if a[i]-a[i-1] == 1:
        ans += c[a[i-1]-1]
print(ans)


Measured memory_bytes: 3060