akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <string>
#include <vector>
#include <algorithm>

#ifndef ULLONG
typedef unsigned long long ULLONG;
#endif
#ifndef LLONG
typedef long long LLONG;
#endif
template <class _T> static _T tp_abs(const _T& a) {
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static void tp_swap(_T& right, _T& left) {
	//	usage:  tp_swap<type name>(a, b);
	_T tmp = right;
	right = left;
	left = tmp;
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void get1int(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void get2int(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void get3int(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}
template <class _T> static _T tp_gcd(_T first, _T second)
{
	_T num1 = first, num2 = second;
	_T remainder = 0, common = 0;

	if (!num1) return num2;
	if (!num2) return num1;

	while (!common) {
		remainder = num1 % num2;

		if (remainder == 0) {
			common = num2;
		}
		else {
			num1 = num2;
			num2 = remainder;
		}
	}
	return(common);
}
template <class _T> static _T tp_lcm(_T first, _T second) {
	_T num1 = first;
	_T num2 = second;

	if ((!num1) || (!num2)) return 0;
	while (num1 != num2) {
		if (num1 < num2) {
			num1 += first;
		}
		else if (num1 > num2) {
			num2 += second;
		}
	}

	return num1;
}
static void D_task();

int main()
{
	D_task();

	fflush(stdout);
	return 0;
}

class D_Work {
public:
	LLONG needTime = 0;
	LLONG endTime = 0;

	static bool sort_end_asc(const D_Work& a, const D_Work& b) {
		return (a.endTime < b.endTime);
	}
};
static void D_task()
{
	int N;
	get1int(N);

	auto works = new D_Work[N + 1];
	for (int i = 0; i < N; i++) {
		get2int<LLONG>(works[i].needTime, works[i].endTime);
	}
	std::sort(works, works + N, D_Work::sort_end_asc);

	const char* ans = "Yes\n";
	LLONG sum = 0;
	for (int i = 0; i < N; i++) {
		sum += works[i].needTime;
		if (sum > works[i].endTime) {
			ans = "No\n";
			break;
		}
	}
	printf(ans);
	delete[] works;
}


Measured memory_bytes: 3328
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline()[:-1]


def solve():
    n, m = [int(x) for x in input().split()]
    a, b = 0, 1e9
    for _ in range(m):
        l, r = [int(x) for x in input().split()]
        a = max(a, l)
        b = min(b, r)
    print(max(0, b - a + 1))
        
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()



"""

1 4
7
RRRR
1 1 0 1
----
4

1 4
47
RCRR
1 1 0 1
----
-1

2 2
10
RR
RR
1 7
4 1
----
4

2 2
10
RR
RR
7 4
7 4
----
-1

3 3
8
RCR
RRC
RRR
1 1 1
1 1 1
1 3 1


3 3
1
RCR
RRC
RRR
1 1 1
1 1 1
1 3 1


"""





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

int main() {
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

int main(){

	int w,h;


	while (1){
		cin >> h >> w;
		if (w == 0 && h == 0) break;

		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				if (i == 0 || i == h - 1 || j == 0 || j == w - 1){
					cout << "#";
				}
				else{
					cout << ".";
				}
			}
			cout << endl;
		}
		cout << endl;
	}


	return 0;
}

Measured memory_bytes: 1152
#include <iostream>

using namespace std;

int main() {
	int N, i, A[100], j, mini, s, k, count = 0;
	cin >> N;
	for (i = 0; i<N; i++)
		cin >> A[i];
	for (i = 0; i<N; i++) {
		mini = i;
		for (j = i; j<N; j++){
			if (A[j] < A[mini]) {
				mini = j; 
			}
		}
		if (mini != i) {
			s = A[i];
			A[i] = A[mini];
			A[mini] = s;
			count++;
		}
	}
	for (k = 0; k<N; k++) {
		if (k<N - 1)  cout << A[k] << " ";
		else cout << A[k] << endl;
	}
	cout << count << endl;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
using namespace std;


int main()
{
    int n;
    vector<int> a;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    vector<int> tmpa(a.size());
    copy(a.begin(), a.end(), tmpa.begin());
    sort(tmpa.begin(), tmpa.end());
    int max = tmpa.back();
    tmpa.pop_back();
    int max2 = tmpa.back();
    bool allFlag = false;
    if (max == max2) {
        allFlag = true;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == max && allFlag == false) {
            vector<int> tmptmpa(a.size());
            copy(a.begin(), a.end(), tmptmpa.begin());
            tmptmpa.erase(tmptmpa.begin() + i);
            sort(tmptmpa.begin(), tmptmpa.end());
            cout << tmptmpa.back() << endl; 
        } else {
            cout << max << endl;
        }
    }
}


Measured memory_bytes: 4084
def ld(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    if l1 == 0 and l2 == 0:
        return 0
    if l1 == 0:
        return l2
    if l2 == 0:
        return l1

    INF = 10**10
    DP = [[INF]*(l2+1) for _ in range(l1+1)] 
    for p1 in range(l1+1):
        DP[p1][0] = p1 
    for p2 in range(l2+1):
        DP[0][p2] = p2 

    for p1 in range(1,l1+1):
        for p2 in range(1,l2+1):
            if s1[p1-1] == s2[p2-1]:
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2-1])
            else:
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2]+1)
                DP[p1][p2] = min(DP[p1][p2],DP[p1][p2-1]+1)
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2-1]+1)
    return DP[l1][l2]

S1 = input() 
S2 = input() 
print(ld(S1,S2))


Measured memory_bytes: 41956
#include <stdio.h>
#define N 100

int main(void){
int a[101],i=0,j,max=0;

//initializing
for(j=1;j<=N;j++){
	a[j]=0;
}


while(scanf("%d",&i)!= EOF){
	a[i]+=1;
}

for(i=1;i<N;i++){
	if(a[i]>max)
	max = a[i];

}

for(i=1;i<N;i++){
	if(max == a[i])
	printf("%d\n",i);

}


return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define ll 				long long
#define ld 				long double
#define fastio 			ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) 		cerr<<#x<<" "<<x<<endl
#define cina(a,n) 		for(ll i = 0;i<n;i++)	cin>>a[i];
#define couta(a,n) 		for(ll i = 0;i<n;i++) cout<<a[i]<<" ";
#define fauto(ar)		for(auto x : ar)	cout<<x<<" ";
#define mod 			1000000007
#define siz 			250
#define f 				first
#define s 				second
#define pb 				push_back
#define endl 			"\n"
#define ci 				cin.ignore()
using namespace std;
int main()
{
	ll h,a = 0,i,j,n;
	cin>>h>>n;
	while(n--)
	{
		cin>>j;
		a += j;
	}
	if(a >= h)
	cout<<"Yes";
	else
	cout<<"No";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>
#include <map>
#include <string>
#include <climits>
#include <set>
#include <sstream>
#include <utility>
#include <ctime>
#include <cassert>
#include <fstream>
using namespace std;
typedef long long LL;
#define MSV(A,a) memset(A, a, sizeof(A))
#define MP make_pair
#define PB push_back
#define INF (int(1e9))
#define INFL (LL(1e18))
#define EPS 1e-12
#define chkbit(s, b) (s & (1<<b))
#define setbit(s, b) (s |= (1<<b))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define MOD 1000000007
#define MAX 100005
#define in(x) scanf("%d", &x)
#define inl(x) scanf("%lld", &x)
#define in2(x, y) scanf("%d %d", &x, &y)
#define inl2(x, y) scanf("%lld %lld", &x, &y)
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const char en = '\n';

int main() {


	int n, i, num = 0, ans = 0;
	cin>>n;
	string s;
	cin>>s;


	queue<int> wpos;

	for(i = 0 ; i < n ;i++) {
		if(s[i] == 'W') wpos.push(i);
	}

	for(i = n-1; i >=0 ;i--) {

		if(wpos.empty()) {
			cout<<ans<<endl;
			return 0;
		}

		if(s[i] == 'R' && wpos.front() < i) {
			ans++;
			wpos.pop();
		}
	}

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 4456
import numpy as np
MOD = 10 ** 9 + 7
N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
for n in range(60): # または、range(60)またはrange(len(bin(max(A))))
    cnt_1 = np.count_nonzero((A>>n)&1)
    cnt_0 = N - cnt_1
    ans += (cnt_1 * cnt_0 * (2 ** n)) % MOD
ans %= MOD
print(ans)

Measured memory_bytes: 48828
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.Stream;

public class Main {
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			br.readLine();
			Map<Integer,Integer> map = new HashMap<>();
			AtomicLong sum = new AtomicLong(0L);
			Stream.of(br.readLine().split(" ")).map(Integer::valueOf).forEach(num -> {
				map.merge(num, 1, (v1,v2)->v1+v2);
				sum.addAndGet(num);
			});

			br.readLine();

			String s = null;
			while((s=br.readLine()) != null) {
				int[] convs=Stream.of(s.split(" ")).mapToInt(Integer::parseInt).toArray();
				int prevKey = convs[0];
				int newKey = convs[1];


				// conv
				Integer cnt = map.remove(prevKey);
				if(cnt != null) {
					sum.getAndAdd(-(cnt.longValue() * (long)prevKey));
					sum.getAndAdd(cnt.longValue() * (long)newKey);

					// merge
					map.merge(newKey, cnt, (v1,v2)-> v1+v2);
				}
				System.out.println(sum);
			}
		} catch(Exception e) {}
	}
}


Measured memory_bytes: 64324
#include <iostream>
#include <algorithm>

using namespace std;

int dp[100001];

int main(void)
{
	int money;
	
	cin >> money;

	for (int i = 1 ; i <= money; i++) {
		dp[i] = i;

		int j = 1;
		while (j <= i) {
			dp[i] = min(dp[i], dp[i - j] + 1);

			j *= 6;
		}
		
		j = 1;
		while (j <= i) {
			dp[i] = min(dp[i], dp[i - j] + 1);

			j *= 9;
		}
	}
	
	cout << dp[money];

	return 0;
}


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

int main() {
  ll n, m;
  cin >> n >> m;
  ll ans = 0;
  ll s_set_c = m / 2;
  if(n >= s_set_c){
    ans += s_set_c;
  }else {
    ans += n;
    m -= 2 * n;
    ans += m / 4;
  }
  cout << ans << endl;
}

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

struct UnionFind{
  vector<int> r;
  UnionFind(int N){
    r = vector<int>(N, -1);
  }
  int root(int x){
    if (r[x] < 0) return x;
    return r[x] = root(r[x]);
  }
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (r[x] > r[y]) swap(x, y);
    r[x] += r[y];
    r[y] = x;
    return true;
  }
  int size(int x){
    return -r[root(x)];
  }
};

int main(){
  int n, m;
  cin >> n >> m;
  UnionFind UF(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    UF.unite(a, b);
  }
  int ans = 0;
  rep(i, n) ans = max(ans, UF.size(i));
  cout << ans << endl;
  return 0;
}


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

struct node{
  int key;
  struct node *next;
  struct node *prev;
};
typedef struct node * NodePointer;
NodePointer nil;

void set(){
  nil = (NodePointer)malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void list(){
    NodePointer n = nil->next;
    int i = 1;

    while(1){
      if(n == nil) break;
      if(i == 0) printf(" ");
      printf("%d",n->key);
      n = n->next; i = 0;
    }
    printf("\n");
  }

NodePointer find(int key){
  NodePointer n;
  for(n = nil;n->next != nil;n = n->next){
    if(n->next->key == key) return n->next;
  }
  return NULL;
}

void deleteNode(NodePointer p){
  p->next->prev = p->prev;
  p->prev->next = p->next;
  free(p);
}

void deleteFirst(){
  NodePointer n = nil->next;
  if(n == nil)return;
  deleteNode(n);
}

void deleteLast(){
  NodePointer n = nil->prev;
  if(n == nil) return;
  deleteNode(n);
}

void delete(int key){
  NodePointer n;
  if((n = find(key)) != NULL) deleteNode(n);
}

void insert(int key){
  NodePointer newnode;
    newnode =(NodePointer)malloc(sizeof(struct node));
    newnode->key = key;
    newnode->next = nil->next;
    newnode->prev = nil;
    nil->next->prev = newnode;
    nil->next = newnode;
}

int main(){
  int n,i,key,j=1;
  char str[20];

  set();

  scanf("%d",&n);

  for(i = 0;i < n;i++){
    scanf("%s",str);
    if(strcmp("insert",str) == 0){
      scanf("%d",&key);
      insert(key);
    }
    if(strcmp("delete",str) == 0){
      scanf("%d",&key);
      delete(key);
    }
    if(strcmp("deleteFirst",str) == 0)deleteFirst();
    if(strcmp("deleteLast",str) == 0)deleteLast();
  }
  list();
  return 0;
}



Measured memory_bytes: 32956
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  long A,B,C,K;
  long UNFAIR = 1000000000000000000;
  cin >> A >> B >> C >> K;
  
  if (K%2 == 0){
    if ((A-B) > UNFAIR){
      cout << "Unfair" << endl;
    } else{
      cout << A - B << endl;
    }
  } else if (K%2 == 1){
    if((B-A) > UNFAIR){
      cout << "Unfair" << endl;
    } else{
      cout << B - A << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;
#define ll long long

int main()
{
    //freopen("aa_input.txt", "r", stdin);
    int test=1;
    //cin>>test;

    while(test--){
       int n, k;
       cin>>n>>k;
       if(n<k) cout<<0<<endl;
       else cout<<10<<endl;
    }
    return 0;
}
/*

riaadmorshed@gmail.com

*/

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <type_traits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <complex>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
int main(){
	ll N, K;
	cin >> N >> K;
	vl A(N);
	REP(i, N){
		cin >> A[i];
	}
	cout << (N-1+(K-2))/(K-1) << endl;
}

Measured memory_bytes: 1152
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int c = 0;

        for (int i = 0; i < s.length(); i++) {
            c += s.charAt(i)=='+'? 1 : -1;
        }
        System.out.println(c);
    }
}


Measured memory_bytes: 22868
<?php
  fscanf(STDIN, "%d %d", $n,$m);
  $sto = [];
  for($i=0; $i<$n; $i++){
      fscanf(STDIN, "%d %d", $a,$b);
      $sto[$a] += $b;
  }
  
  ksort($sto);
//   print_r($sto);
  
  $dol = 0;
  foreach($sto as $cash => $hon){
      $dol += $cash*min($m, $hon);
      $m -= min($m, $hon);
  }
  echo $dol;

Measured memory_bytes: 13048
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
A = tuple(map(int, read().split()))

if N == 2:
    print(A[1] - A[0])
    exit()

dp = [10 ** 10] * N
dp[1] = abs(A[1] - A[0])
dp[2] = abs(A[2] - A[0])

for i in range(3, N):
    dp[i] = min(dp[i - 1] + abs(A[i] - A[i - 1]), dp[i - 2] + abs(A[i] - A[i - 2]))

print(dp[-1])

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

#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define ALL(v) (v).begin(), (v).end()
#define INF 1e09
struct P{
  int x; int y; bool got=false;
};

using namespace std;

int main(){
  int n, m;
  while(cin >> n >> m and n + m){
    vector<int> t(n), h(m);
    REP(i, n) cin >> t[i];
    REP(i, m) cin >> h[i];
    int tsum, hsum;
    tsum = accumulate(ALL(t), 0);
    hsum = accumulate(ALL(h), 0);
    int dif = tsum - hsum;
    int tans = 0; int hans = 0;
    sort(ALL(t));
    sort(ALL(h));
    REP(i, n) {
      REP(j, m) if((t[i] - h[j]) * 2 == dif) { tans = t[i]; hans = h[j]; break; }
      if (tans != 0) break;
    }
    if(tans == 0)
      cout << -1 << endl;
    else
      cout << tans << " " << hans << endl;
  }
}

Measured memory_bytes: 3004
m,d=map(int,input().split( ))
ans=0
for mon in range(1,m+1):
    for day in range(1,d+1):
        d1=day%10
        d10=day//10
        if d1>1 and d10>1 and d1*d10==mon:
            ans+=1
print(ans)


Measured memory_bytes: 2940
use proconio::input;
use std::collections::HashSet;

fn main() {
    input! {
        n: u32,
        strs: [String; n],
    }

    let mut map = HashSet::new();
    let mut count = 0;
    for s in &strs {
        let op = map.get(s);
        if op.is_none() {
            count+=1;
            map.insert(s);
        } 
    }

    println!("{}", count);

}


Measured memory_bytes: 18600
// https://atcoder.jp/contests/abc086/tasks/abc086_a
#include <bits/stdc++.h>
using namespace std;

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

  (a * b % 2 == 0) ? cout << "Even" : cout << "Odd";
  return 0;
}


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

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

    int s, w;
    cin >> s >> w;
    if(s <= w){
        cout << "unsafe" << endl;
    }else{
        cout << "safe" << endl;
    }

    return 0;
}

Measured memory_bytes: 3580
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

S = gets.chomp

sa = 10 ** 5
S.split('').each_cons(3) do |arr|
  stock = (753 - arr.join.to_i).abs
  sa = stock if stock < sa
end

puts sa


Measured memory_bytes: 14368
#include <iostream>
#include <string>

using namespace std;

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

	int ans = 0;
	string t;
	for (int i = 1; i <= n; i++) {
		t = to_string(i);
		if (t.size() % 2 == 1) {
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lp(n) for(int i = 0; i < n; i++)
#define lpp(i, n) for(int i = 0; i < n; i++)
struct a{
  char m[36];
  int n[36];
};
using namespace std;

void bs(struct a A, int n) {
  int *c = A.n;
  char *m = A.m;
  lp(n) {
    for(int j = n-1; j >= i+1; j--) {
      if(c[j] < c[j-1]) {
	swap(c[j], c[j-1]);
	swap(m[j], m[j-1]);
      }
    }
  }
  lp(n) cout << m[i] << c[i] << ((n-1==i)?"\n": " ");
  cout << "Stable" << endl;
}

void ss(struct a A, int n) {
  struct a B = A;
  int *a = A.n;
  char *m = A.m;
  int minj;
  int r = 0;
  lp(n) {
    minj = i;
    for(int j = i; j <= n-1; j++) {
      if(a[j] < a[minj]) minj = j;
    }
    swap(a[i], a[minj]);
    swap(m[i], m[minj]);
  }
  int *c = B.n;
  char *m1 = B.m;
  lp(n) {
    for(int j = n-1; j >= i+1; j--) {
      if(c[j] < c[j-1]) {
	swap(c[j], c[j-1]);
	swap(m1[j], m1[j-1]);
      }
    }
  }
  lp(n) if(m[i] != m1[i]) r = 1;
  lp(n) cout << m[i] << a[i] << ((n-1==i)?"\n": " ");
  cout << (r? "Not stable" : "Stable") << endl;
  
}

int main() {
  struct a A;
  int n, c=0;
  char s;
  cin >> n;
  lp(n) scanf(" %c%d", &A.m[i], &A.n[i]);
  
  bs(A, n);
  ss(A, n);
  
  return 0;
}



Measured memory_bytes: 3244
/**
*    author:  souzai32
*    created: 23.08.2020 19:40:40
**/

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
typedef long long ll;
#define mod 1000000007
using namespace std;

int main() {

    ll n,a,b;
    cin >> n >> a >> b;
    ll ans=0;
    vector<ll> x(n);
    rep(i,n) cin >> x[i];

    rep(i,n-1) ans+=min(a*(x[i+1]-x[i]),b);

    cout << ans << endl;

    return 0;
}

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

const int MAXN = 112345;
const int LOGN = 20;

int n;
long long l;

long long v[MAXN];	// Position of each hotel

bool vis[MAXN];
vector <int> g[MAXN];	// Tree built on hotels you can reach
int memo[MAXN][LOGN];	// LCA Memoization. First => Node, Second => Dist


void dfs (int x) {
	for (int i = 1; i < LOGN; ++i) {
		if (memo[x][i - 1] == -1) break;
		memo[x][i] = memo[memo[x][i - 1]][i - 1];
	}
	
	vis[x] = true;
	for (int i = 0; i < g[x].size(); ++i) {
		int y = g[x][i];
		memo[y][0] = x;
		dfs (y);
	}
}

int getdist (int x, int y) {
	int ans = 0;
	for (int i = LOGN - 1; i >= 0; --i) {
		if (memo[x][i] != -1 && memo[x][i] <= y) {
			ans += (1 << i);
			x = memo[x][i];
		}
	}

	return ans + (x != y);
}

// L = 10
// 1 3 6 13 15 18 19 29 31

// 1 8
// 3 7


void buildgraph () {
	int r = 0;
	for (int i = 0; i < n - 1; ++i) {
		while (r < n && v[r] - v[i] <= l) ++r;

		g[r - 1].push_back (i);
	}

	memset (memo, -1, sizeof memo);
	for (int i = n - 1; i >= 0; --i)
		if (!vis[i])
			dfs (i);
}

int main () {

	cin >> n;

	for (int i = 0; i < n; ++i) scanf ("%lld", v + i);
	cin >> l;

	buildgraph ();

	int q;
	cin >> q;

	while (q--) {
		int x, y;
		scanf ("%d %d", &x, &y);
		--x; --y;
		if (x > y) swap (x, y);

		printf ("%d\n", getdist (x, y));
	}

	return 0;
}

Measured memory_bytes: 20864
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		no2();
	}

	static void no2() {
		try (Scanner sc = new Scanner(System.in)) {
			int N = sc.nextInt();
			long[] a = new long[N];
			long[] b = new long[N];

			long[] d = new long[N];
			long[] dc = new long[N];

			long asum = 0;
			long bsum = 0;

			long plus1 = 0;
			long plus2 = 0;
			long minus = 0;

			for (int i = 0; i < N; i++) {
				a[i] = sc.nextLong();
				asum += a[i];
			}

			for (int i = 0; i < N; i++) {
				b[i] = sc.nextLong();
				bsum += b[i];

				long t = b[i] - a[i];
				if (t <= 0) {
					minus -= t;
				} else {
					if (t % 2 == 0) {
						plus1 += t;
					} else {
						plus1 += t - 1;
						plus2++;
					}
				}
			}

			long t = plus1 - (minus * 2);
			long tt = minus + plus2 + t;

			if (t < 0) {
				System.out.println("No");
				return;
			}

			if (tt > bsum - asum) {
				System.out.println("No");
			} else {
				System.out.println("Yes");
			}
		}
	}

	static void no1() {
		try (Scanner sc = new Scanner(System.in)) {
			long x = sc.nextLong();
			long y = sc.nextLong();

			if (x % y == 0) {
				System.out.println("-1");
				return;
			}

			long i = 1;
			long t = x;
			while (true) {
				if (t % y != 0) {
					System.out.println(t);
					return;
				}
				if (t > 1000000000000000000L - x) {
					System.out.println("-1");
					return;
				}
				t += x;
			}
		}
	}

}


Measured memory_bytes: 42352
#include <bits/stdc++.h>
#define LL long long
const int maxn=205;
LL w[maxn],v[maxn];
LL  f[maxn][maxn<<2][maxn];
LL n,W;
void dp();
int main() {
    scanf("%lld%lld",&n,&W);
    for(int i=1; i<=n; ++i) {
        scanf("%lld%lld",&w[i],&v[i]);
    }
    LL tem=w[1];
    for(int i=1; i<=n; ++i) {
        w[i]-=tem;
    }
    dp();
    LL ret=0;
    for(int j=0; j<301; ++j) {
        for(int m=0; m<=n; ++m) {
            if(j+m*tem<=W)ret=std::max(f[n][j][m],ret);
        }
    }
    printf("%lld\n",ret);
    return 0;
}
void dp() {
    for(int i=1; i<=n; ++i) {
        for(int j=0; j<301; ++j) {
            for(int m=1; m<=n; ++m) {
                if(j<w[i]) f[i][j][m]=f[i-1][j][m];
                else f[i][j][m] = std::max(f[i-1][j-w[i]][m-1]+v[i],f[i-1][j][m]);
            }
        }
    }
}


Measured memory_bytes: 131840
n = int(input())
a = list(map(int, input().split()))

data = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    data[i][0] = a[i]
    data[i][1] = i + 1
data.sort()
for i in range(n):
    print(data[i][1], end = " ")


Measured memory_bytes: 23232
#include <stdio.h>

int main() {
    int yen;
    int gold = 0;
    scanf("%d", &yen);
    int resto = yen % 500;
    
    if (yen == 500)
        gold = 1000;
    else if (yen > 500) {
        gold = ((yen / 500)*1000) + ((resto / 5)*5);
    } else 
        gold = (resto / 5)*5;
    
    printf("%d\n", gold);
    
    return 0;
}


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

int main(){
    string S;
    int price = 700;
    cin >> S;
    for (int i = 0; i <= 3; i++)
    {
        if (S[i] == 'o') price += 100;
    }
    cout << price << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100005
char s[MAXN];
int main()
{
	scanf("%s",s);
	int len=strlen(s);
	for(int i=0;i<=len-2;i++)
	{
		if(s[i]==s[i+2])
		{
			printf("%d %d\n",i+1,i+3);
			return 0;
		}
		if(s[i]==s[i+1])
		{
			printf("%d %d\n",i+1,i+2);
			return 0;
		}
	}
	printf("-1 -1\n");
	return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()

mod = 10**9+7

dic = {}
for i in range(N):
    if S[i] in dic:
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1

ans = 1
for key in dic:
    ans *= dic[key]+1
    ans %= mod

ans -= 1
print(ans)

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

/* nCm を計算 */
ll choose2(ll n){
  return (n)*(n-1)/2;
}

#define DEBUG (0)

int main()
{
  int n = 0;
  cin >> n;
  vector<int> a(n);		//入力値を格納する配列, 1 <= a(n) <= N
  
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }

  vector<int> cnt(n);		//a(n)の値が何個あるかの配列 1が３個ならc[0]=3

#if 0 //DEBUG
  for(int i = 0; i < n; i++){
    cout << "a[i]: " << a[i] <<" ,cnt[i]: " << cnt[a[i]-1] << endl;
  }
  cout << "------------" << endl;
#endif
  
  for(int i =0; i < n; i++){
    cnt[a[i]-1]++;		//a(n)=1の場合はc[0]を１インクリメント
  }

  for(int i =0; i < n; i++){
#if DEBUG
    cout << "a[i]: " << a[i] <<" ,cnt[i]: " << cnt[i] << endl;
#endif
  }
  
  ll total = 0;	/* 組み合わせ合計値 */
  for(int i = 0; i < n; i++){
    total += choose2(cnt[i]);		//k番目を削除しない場合の組み合わせ総数
  }

#if DEBUG
  cout << "total: " << total << endl;
#endif
  
  /* totalからk番目を削除した場合の組み合わせ数を引いて出力 */
  for(int i = 0; i < n; i++){
    /* 「nC2」を引いて「n-1C2」 を足す */
    int diff = -1*choose2(cnt[a[i]-1]) + choose2(cnt[a[i]-1]-1);
#if DEBUG
    cout << "diff: " << diff << " answer: " << (total + diff) << endl;
#else
    cout << (total + diff) << endl;
#endif
  }
}

Measured memory_bytes: 4096
//includes
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#include<numeric>
#include<assert.h>
#include<cstring>
#include<unordered_map>
#include<bitset>

//macros and consts
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define FORE(i,a) for(auto &i : a)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define accm accumulate
#define Fi first
#define Se second
#define INF 1e9
#define llINF (1LL<<60)
#define mINF -1e9
#define mllINF -(1LL<<60)
#define endl "\n"
#define CONT continue
#define BRK break
#define modulo(n, m) (((n)%(m)+(m))%m)

//shorter types
using namespace std;
using ll = long long;
using vi = std::vector<int>;
using vc = std::vector<char>;
using vll = std::vector<long long>;
using vs = std::vector<string>;
using Mi = map<int,int>;
using Mll = map<ll,ll>;
using UMi = unordered_map<int,int>;
using UMll = unordered_map<ll,ll>;
using Pi = pair<int,int>;
using Pll = pair<ll,ll>;
using vPi = vector<Pi>;
using vPll = vector<Pll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using pqgi = priority_queue<int,vector<int>,greater<int>>;
using pqsi = priority_queue<int,vector<int>,less<int>>;
using pqgll = priority_queue<int,vector<int>,greater<int>>;
using pssll = priority_queue<int,vector<int>,less<int>>;
template<class T>
using vec = vector<T>;
#define int long long

int N,M;
vector<int> A;
bool check(int x){
	int sum = 0;
	for(int i = 0 ; i < N ; i++){
		int over = lower_bound(all(A), x - A[i]) - A.begin();
		sum += (N - over);
	}
	return sum < M;
}
//here begins your code
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  cin >> N >> M;

  A.resize(N);
  for(int i = 0 ; i < N ; i++){
  	cin >> A[i];
  }
  sort(all(A));

  int ng = 0, ok = llINF;
  while(abs(ok - ng) > 1){
  	int mid = (ok + ng) >> 1;
  	if(check(mid)) ok = mid;
  	else ng = mid;
  }
  vector<int> wa(N + 1);
  for(int i = 0 ; i < N ; i++){
 	wa[i + 1] = wa[i] + A[i];
  }
  int ans = 0;
  for(int i = 0 ; i < N ; i++){
  	int pos = lower_bound(A.begin(),A.end(),ok - A[i]) - A.begin();
  	int cnt = N - pos;
  	ans += cnt * A[i] + (wa[N] - wa[pos]);
  	M -= cnt;
  }
  ans += M * ng;
  cout << ans << endl;
  //check types
  //do not eb if you resize
  //resize before you access by idx
  return 0;
} 

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


typedef long long ll;
using namespace std;
template <typename T> void print(T vec) {for(auto d: vec) cout<<d<<' ';cout<<'\n';}
template<typename T> void print2D(T mat) {for(auto vec:mat) print(vec);}


int64_t n, W;
vector<ll> weight(n), value(n);




ll knapSack(ll W, ll n, vector<vector<ll>> &dp) {
    if(n < 0 || W == 0) return 0;
    if(dp[n][W] != -1) return dp[n][W];
    if(weight[n] > W) dp[n][W] =  knapSack(W, n - 1, dp);
    else dp[n][W] = max(value[n] + knapSack(W - weight[n], n - 1, dp), knapSack(W, n - 1, dp)); 
    return dp[n][W];
}

int main() {
    
    cin>>n>>W;
    int temp;
    weight.resize(n);
    value.resize(n);
    vector<vector<ll>> dp(n, vector<ll>(W+1, -1));
    for(int i = 0; i< n;i++) {
        cin>>weight[i]>>value[i];
    }
    // cout<<func(W, value, weight, n);
    cout<<knapSack(W, n - 1, dp)<<'\n';
    // print2D(dp);
    return 0;
}

Measured memory_bytes: 79488
#include <stdio.h>
int divisor(int n)
{
	int i,c=0;
	for(i=1; i<=n; i++){
		if(n%i==0){
			c=c+1;
		}
	}
	return c;
}
int main(void)
{
	int n,i,c=0;
	scanf("%d",&n);
	for(i=1; i<=n; i=i+2){
		if(divisor(i)==8){
			c=c+1;
		}
	}
	printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

constexpr char S = '#';
vector<string> s;
vector<vector<int>> ans;
int col = 1;

void splitcake(const int xs,const int xe,const int ys,const int ye) {
    // cerr << xs << " " << xe << " " << ys << " " << ye << endl;
    int x1 = -1;
    int y1 = -1,y2 = -1;
    for(auto y = ys; y <= ye; y++) {
        auto pos = s[y].find(S,xs);
        if (pos != string::npos) {
            if (y1 == -1) y1 = y;
            else {
                y2 = y;
                break;
            }
        }
    }

    if (y2 != -1) {
        // ichigo 2 line over
        // cerr << "ysplit" << endl;
        splitcake(xs,xe,ys,y1);
        splitcake(xs,xe,y1+1,ye);
    } else {
        // ichigo 1 line
        x1 = s[y1].find(S,xs);
        auto pos = s[y1].find(S,x1+1);
        if (pos > xe) {
            // paint
            // cerr << "p" << col << endl;
            for(int y = ys; y <= ye; y++) for(int x = xs; x <= xe; x++) ans[y][x] = col;
            col++;
        } else {
            // cerr << "xsplit" << endl;
            splitcake(xs,x1,ys,ye);
            splitcake(x1+1,xe,ys,ye);
        }
    }

}

int main(void)
{
    IOS
    int h, w, k;
    cin >> h >> w >> k;
    s.resize(h);
    REP(i,h) cin >> s[i];
    ans.resize(h);
    REP(i,h) ans[i].resize(w);

    splitcake(0,w-1,0,h-1);

    for(auto v:ans) {
        REP(i,v.size()-1) cout << v[i] << " ";
        cout << v.back() << endl;
    }

    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_K = 100005;
const ll MOD = 1e9+7;
ll N,K;
ll cnt[MAX_K];

ll pow(ll x, ll n) //x^n
{
	if (n == 0) return 1;
	if (n == 1) return x;
	if (n % 2 == 1)
	{
		return pow(x,n-1) * x % MOD;
	}
	else
	{
		ll p = pow(x,n/2);
		return p * p % MOD;
	}
}

int main()
{
	cin >> N >> K;
	ll ans = 0;
	for (int i = K; i > 0; --i)
	{
		cnt[i] = pow(K/i,N);
		ll temp = i+i;
		while(temp <= K)
		{
			cnt[i] = (cnt[i] - cnt[temp] + MOD) % MOD;
			temp += i;
		}
		ans = (ans + i * cnt[i] % MOD) % MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4400
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  ll n;cin>>n;
  ll MAX=0;
  ll ans=0;
  rep(i,n){
    ll a,b;cin>>a>>b;
    if(a>MAX){
      ans=a+b;
      MAX=a;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define REP(a) for(i = 0; i < a; i++)
int main(void) {
    int n,k,i,sum = 0;
    scanf("%d",&n);
    scanf("%d",&k);
    int x[n];
    REP(n) {
        scanf("%d",&x[i]);
        if (x[i] < k - x[i]) {
            sum += x[i];
        } else {
            sum += k - x[i];
        }
    }
    printf("%d\n",sum * 2);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

signed main(){
    ll a,b;
    double h,m;
    cin >> a >> b >> h >> m;

    cout << setprecision(15) << sqrt(a*a + b*b - 2*a*b*cos(acos(-1)/30.0*fabs(m - 5*h - m / 12.0))) << endl;
    return 0;
}

Measured memory_bytes: 4124
a = input().split()
tg = a[0]
ok_nums = set(str(i) for i in range(10))
ng_nums = set(i for i in input().split())
ok_nums = ok_nums - ng_nums
rt = 0
i = int(tg)
intg = int(tg)
while intg > rt:
  if ok_nums >= set(d for d in str(i)):
    rt = i
  else:
    i+=1

print(rt)

Measured memory_bytes: 9052
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<vector<ll> > mat;

int vis[11][100005],ans[100005],a[100005],d[100005],c[100005],dis[100005];

vii v[100005];

int main()
{ios_base::sync_with_stdio(false);
int n,m,qq;
cin>>n>>m;

while(m--)
{
	int a,b;
	cin>>a>>b;
	v[a].pb(b);
	v[b].pb(a);
}

cin>>qq;
rep(i,0,qq-1)
{
	cin>>a[i]>>d[i]>>c[i];
}
rep(i,1,n)dis[i]=1e9+7;
ren(i,qq-1,0)
{
	int at=a[i];
	dis[at]=0;
	vii v1;
	
	queue<int> q;
	q.push(at);
	while(!q.empty())
	{
		int at=q.front();
		v1.pb(at);
		q.pop();
		int f=0;
		rep(ii,0,10)f+=vis[ii][at];
		if(f==0)
		{
			ans[at]=c[i];
			vis[d[i]-dis[at]][at]=1;
			tr(v[at],it)
			{
				int to=*it;
				if(1+dis[at]<dis[to]&&1+dis[at]<=d[i])
				{
					dis[to]=1+dis[at];
					q.push(to);
				}
			}
		}
		else
		{
			int f1=0;
			rep(ii,d[i]-dis[at],10)f1+=vis[ii][at];
			if(f1==0)
			{
				vis[d[i]-dis[at]][at]=1;
				tr(v[at],it)
				{
					int to=*it;
					if(1+dis[at]<dis[to]&&1+dis[at]<=d[i])
					{
						dis[to]=1+dis[at];
						q.push(to);
					}
				}
			}
		}
	}
	tr(v1,it)dis[*it]=1e9+7;
}
rep(i,1,n)
{
	ol(ans[i]);on;
}

return 0;
}


Measured memory_bytes: 13316
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
const int MOD=2019;
typedef long long ll;
int a[100005],b[100005];
int main()
{
    int n;
    cin>>n;
    b[0]=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(i%2==0)
            b[0]+=a[i];
        else
            b[0]-=a[i];
    }
    for(int i=1;i<n-1;i++)
    {
        b[i]=2*a[i-1]-b[i-1];
    }
    b[n-1]=2*a[n-1]-b[0];
    for(int i=0;i<n;i++)
    {
        cout<<b[i];
        if(i!=n-1)
            cout<<' ';
        else
            cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 2048
from collections import deque

n, q = map(int, input().split())
Adj = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj[a-1].append(b-1)
    Adj[b-1].append(a-1)

P, X = [], []
Counter = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    Counter[p-1] += x

visited = set()
visited.add(0)

dq = deque()
dq.append(0)

while dq:
    x = dq.popleft()
    for j in Adj[x]:
        if j not in visited:
            visited.add(j)
            dq.append(j)
            Counter[j] += Counter[x]
ans = ''
for i in range(n-1):
    ans += str(Counter[i]) + ' '
ans += str(Counter[n-1])
print(ans)

Measured memory_bytes: 63772
#include<iostream>
#include<math.h>
using namespace std;

int main(){
  int H,N,sum=0;
  cin>>H>>N;
  
  int A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
  }
  
  if(sum>=H){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }

  return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

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

    li h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    cout << (h2 - h1) * 60 + (m2 - m1) - k << endl;


    return 0;
}

Measured memory_bytes: 3648
import heapq

N, M = map(int, input().split())
D = {}
for n in range(N):
    a, b = map(int, input().split())
    D.setdefault(a, []).append(b)

hq = []
res = 0
for n in range(1, M + 1):
    if n in D.keys():
        AD = D[n]
        for l in AD:
            heapq.heappush(hq, -l)
    if hq:
        res -= heapq.heappop(hq)

print(res)


Measured memory_bytes: 27348
# D
n = int(input())
A_list = list(map(int, input().split()))

# cumsum from left
a = 0
A_left = []
for i in range(n):
    a += A_list[i]
    A_left.append(a)
    
res = A_left[n-1]
i = 0
j = 1
k = 2
while j <= n - 3:
    while True:
        if abs(A_left[j] / 2 - A_left[i]) > abs(A_left[j] / 2 - A_left[i+1]):
            i += 1
        else:
            break
            
    while True:
        if abs((A_left[n-1] - A_left[j]) / 2 - (A_left[n-1] - A_left[k])) > abs((A_left[n-1] - A_left[j]) / 2 - (A_left[n-1] - A_left[k+1])):
            k += 1
        else:
            break
    # print(i, j, k)
    a, b, c, d = A_left[i], A_left[j]-A_left[i], A_left[k]-A_left[j], A_left[n-1]-A_left[k]
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
    j += 1
    
print(res)

Measured memory_bytes: 95096
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

int N;

bool ok(vector<int> &a) {
	for (int num : a) {
		if (num >= N) return false;
	}
	return true;
}

signed main() {
	cin >> N;

	vector<int> a;
	inputVector(a, N);

	int ret = 0;
	while (!ok(a)) {
		int cntall = 0;
		int cnt[50];
		memset(cnt, 0, sizeof cnt);
		rep(i, a.size()) {
			int dif = a[i] - N + 1;
			int tmp = (dif + N - 1) / N;
			cnt[i] = tmp;
			cntall += tmp;
			a[i] -= tmp * N;
		}
		rep(i, a.size()) {
			a[i] += cntall - cnt[i];
		}
		ret += cntall;
	}

	cout << ret << endl;

    return 0;
}


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

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

#define ll long long
#define vl vector<ll>
#define vll vector<vl>

const ll mod = 1000000007;

bool done[100010];
int par[100010];
int par_d[100010];

int main() {
	int n;
	ll k;
	cin >> n >> k;
	vector<int> e[100010];
	int a, b;
	rep(i, n-1)
	{
		cin >> a >> b;
		a--;
		b--;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	queue<int> q;
	q.push(0);
	int ans=1;
	bool muri=false;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		done[now]=true;
		if(par[now]==now) ans=ans*k%mod;
		else
		{
			par_d[par[now]]++;
			if(par_d[par[now]]>=k)
			{
				muri=true;
				break;
			}
			//cout << now << ' ' << (k-par_d[par[now]]) << endl;
			ans=ans*(k-par_d[par[now]])%mod;
		}
		rep(i, e[now].size())
		{
			int to=e[now][i];
			if(!done[to])
			{
				par_d[to]++;
				par[to]=now;
				q.push(to);
			}
		}
	}
	if(muri) cout << '0' << endl;
	else cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7416
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
typedef long double ld;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const int inf = 1e5;
//typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; };
int main(){
  int ddx[2]={0,1}, ddy[2]={1,0};
  int H,W;  cin>>H>>W;
  string s[H];
  rep(i,0,H) cin>>s[i];
  int b=0;
  rep(i,0,H){
    rep(j,0,W){
      if(s[i][j]=='#') b++;
    }
  }
  string ans="Impossible";
  if(b == H+W-1) ans="Possible";
  cout << ans << endl;
  return 0;
}


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

using namespace std;
typedef set<int> si;
const int N=2e5+10;
int n; si a[N];
queue<si*> q;
priority_queue<int, vector<int>, greater<int> > vals;

si* smer (si* s, si* t) {
    if (s->size()<t->size()) swap(s,t);
    while (!t->empty()) {
        s->insert(*(t->begin()));
        t->erase(t->begin());
    }
    return s;
}

int main()
{/*
    freopen("input.txt","r",stdin); //*/
    scanf("%d",&n);
    for (int i=1; i<=n; ++i) {
        int u; scanf("%d",&u);
        a[i].insert(u); vals.push(u);
    }
    for (int i=1; i<=n; ++i) {
        q.push(&a[i]);
    }
    long long ans = 0ll;
    while (!vals.empty()) {
        int u = vals.top(); vals.pop();
        si* dummy = q.front(); q.pop();
        while (!dummy->count(u)) {
            dummy = smer(dummy, q.front());
            q.pop();
        }
        dummy->erase(u);
        ans += dummy->size();
        if (!dummy->empty())
            q.push(dummy);
    }
    printf("%lld\n",ans);
    return 0;
}



Measured memory_bytes: 24084
n = int(input())
S = [input() for _ in range(n)]
ans = 0
c = {}

for s in S:
    s = "".join(sorted(s))
    if s not in c.keys():
        c[s] = 1
    else:
        ans += c[s]
        c[s] += 1


print(ans)

Measured memory_bytes: 100604
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

int main(){
    int n, k; cin >> n >> k;
    vector<int> xs(n);
    for(int i=0; i<n; ++i){
        cin >> xs[i];
    }
    long long ans=numeric_limits<long long>::max();
    for(int i=0; i<n-k+1; ++i){
        long long xl=xs[i], xr=xs[i+k-1];
        long long dl=abs(xl), dr=abs(xr);
        long long d=xl*xr>0 ? max(dl, dr) : min(dl*2+dr, dl+dr*2);
        ans=min(ans, d);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#define llint long long
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;
typedef pair<P, int> T;

struct edge{
	llint to, cost;
	edge(){}
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

llint n, m;
vector<edge> G[100005];
llint dist[100005];

void dijkstra()
{
	for(int i = 1; i <= n; i++) dist[i] = inf;
	dist[1] = 0;

	priority_queue< P, vector<P>, greater<P> > Q;
	Q.push( make_pair(0, 1) );

	llint v, d;
	while(Q.size()){
		d = Q.top().first;
		v = Q.top().second;
		Q.pop();
		if(dist[v] < d) continue;
		for(int i = 0; i < G[v].size(); i++){
			if(dist[G[v][i].to] > d + G[v][i].cost){
				dist[G[v][i].to] = d + G[v][i].cost;
				Q.push( make_pair(dist[G[v][i].to], G[v][i].to) );
			}
		}
	}
}

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

  cin >> n >> m;
	for(int i = 1; i < n; i++) G[i+1].push_back(edge(i, 0));

	llint l, r, c;
	for(int i = 1; i <= m; i++){
		cin >> l >> r >> c;
		G[l].push_back(edge(r, c));
	}
	dijkstra();

	if(dist[n] > inf/2) dist[n] = -1;
	cout << dist[n] << endl;

  return 0;
}


Measured memory_bytes: 10232