akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  N*=2;
  vector<int> a(N);
  for(int i=0;i<N;i++)cin>>a.at(i);
  sort(a.begin(),a.end());
  int ans=0;
  for(int i=0;i<N;i+=2)ans+=a.at(i);
  cout<<ans<<endl;
}

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


int main(void) {
    int N;
    cin >> N;
    vector<pair<int, int> >A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i].first;
        A[i].second = (i + 1);
    }
    sort(A.begin(), A.end());
    for(int i = 0; i < N; i++) {
        cout << A[i].second;
        if(i == N - 1) {
            cout << '\n';
        } else {
            cout << ' ';
        }
    }
    return 0;
}

Measured memory_bytes: 1536
n = int(input())
a = [i for i in map(int , input().split())]
cnt = [1 for i in range(n)]
j = 0

for i in range(1,n) :
    if a[i] == a[i-1] :
        cnt[j] += 1
    else :
        j += 1


ans = 0
for i in range(j+1) :
    if cnt[i] != 1 :
        ans += cnt[i] // 2

print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>

int main()
{
	char ch[200010],ch2[200010];
long long int i,j,count=0;

gets(ch);
gets(ch2);

for(i=0;i<strlen(ch);i++)
{
	if(ch[i] !=ch2[i]) count++;
}

printf("%lld", count);
	return 0;
}

Measured memory_bytes: 1972
#include<stdio.h>
#include<math.h>

int main() {

    int i, N, K, a, b, c;
	long int sum=0, sum_1=0, sum_0=0, times;



	scanf("%d %d", &N, &K);


	times = N / K;

	if (K % 2 != 0) {
		printf("%ld\n", times*times*times);
	}
	else {
		for (i = K / 2; i <= N; i++) {
			if (i%K == 0) {
				sum_0++;
			}
			else if (i%K == K / 2) {
				sum_1++;
			}
		}

		printf("%ld\n", sum_1*sum_1*sum_1 + sum_0*sum_0*sum_0);
	}

	return 0;
}



Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define endl "\n"
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 3e5 + 7;
const int P = 1e9 + 7;

int a[N], b[N], n, ok, l, r, mid, ans;

bool check(int mid) {
	rep(i, 1, n*2) if (a[i] >= mid) b[i] = 1;else b[i] = 0;
	int t1 = 0, t2 = 0;
	b[0] = b[1];
	b[n*2] = b[n*2-1];
	rep(i, n+1, n*2+1) {
		t1++;
		if (b[i] != (b[n] ^ (t1 & 1))) break;
	}
	per(i, 0, n) {
		t2++;
		if (b[i] != (b[n] ^ (t2 & 1))) break;
	}
	if (t1 < t2) return b[n + t1 - 1];else return b[n - t2 + 1];
}

int main(){
	//freopen("a.in", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	//n = 10000;
	rep(i, 1, n*2) cin >> a[i];
	//rep(i, 1, n * 2) a[i] = i;
	//random_shuffle(a+1, a+n*2);
	l = 1; r = n * 2 - 1; ans = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (check(mid)) ans = mid, l = mid + 1;
		else r = mid - 1;
	} 
	cout << ans;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
main(){
  double l,r;
  double eye[4]={1.1,0.6,0.2,0.0};
  int ans[8]={0};
  while(cin>>l>>r){
    for(int i=0;i<4;i++){
      if(l>=eye[i]){
	ans[i]++;
	break;
      }
    }
    for(int i=0;i<4;i++){
      if(r>=eye[i]){
	ans[i+4]++;
	break;
      }
    }
  }
  for(int i=0;i<4;i++){
    cout<<ans[i]<<" "<<ans[i+4]<<endl;  
  }
}

Measured memory_bytes: 1224
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.EducationalDP
{
    class A
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            int[] hs = ReadInts();
            long[] dp = new long[n];
            dp[0] = 0;
            dp[1] = Math.Abs(hs[0] - hs[1]);
            for(int i = 2; i < n; i++)
            {
                dp[i] = Math.Min(dp[i - 1] + Math.Abs(hs[i] - hs[i - 1]),
                    dp[i - 2] + Math.Abs(hs[i] - hs[i - 2]));
            }
            Console.WriteLine(dp[n - 1]);
        }

        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

const int mx=2e6;

int main(){
	int n,i;
	long long int ans=0,sum=0;
	cin>>n;
	vector<int> arr(n);
	for(i=0;i<n;i++){
		cin>>arr[i];
		sum+=arr[i];
	}

	for(i=0;i<n;i++){
		sum-=arr[i];
		//v = sum%mod;
		ans+=((sum%mod)*(arr[i]%mod)+mod)%mod;
	}
	cout<<ans%mod<<endl;
}

Measured memory_bytes: 4048
n = int(input())
str = input()
char_list = list(str)
#del_num = []

count =0
ans =0

#dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
for i in range(len(char_list)-1):
    if char_list[i] == char_list[i+1]:
        #del_num.append(i+1)
        count += 1

ans = n - count

print(ans)


Measured memory_bytes: 4084
import heapq

N,M=map(int,input().split())
A = [int(x) for x in input().split()]
heapq.heapify(A)
Q = [[int(x) for x in input().split()] for y in range(M)]

Q = sorted(Q,key=lambda x: -x[1])

for i in range(M):
  ch = False
  for j in range(Q[i][0]):
    tmp = int(A[0])
    if tmp >= Q[i][1]:
      ch =True
      break
    else:
      heapq.heappop(A)
      heapq.heappush(A,Q[i][1])
  if ch :
    break
print(sum(A))

Measured memory_bytes: 31056
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
ll now,ans=1,K,n,k;
vector<ll> neg,pos,zero;
vector<pair<ll,ll> > li;
int main(){
  // freopen("input.txt","r",stdin);
  cin>>n>>k;
  K = k;
  for(int i = 1;i <= n;i++){
    cin>>now;
    if(now > 0){
      pos.push_back(now);
      li.push_back({now,1});
    }
    else if(now < 0){
      neg.push_back(abs(now));
      li.push_back({abs(now),-1});
    }
    else{
      zero.push_back(now);
      li.push_back({now,1});
    }    
  }
  sort(pos.begin(),pos.end());
  sort(neg.begin(),neg.end());
  sort(li.begin(),li.end());
  int sp = pos.size()-1;
  int sn = neg.size()-1;
  if(k&1){
    if(pos.size()){
      ans = pos[sp];
      sp--;
      k--;
    }
  }
  while(k and (sp > 0 or sn > 0)){
    ll a = -inf,b = -inf;
    if(sp >= 1){
      a = pos[sp]*pos[sp-1];
    }
    if(sn >= 1){
      b = neg[sn]*neg[sn-1];
    }
    if(a > b){
      ans = (ans*(a%mod))%mod;
      k -= 2;
      sp -= 2;
    }
    else{
      ans = (ans*(b%mod))%mod;
      k -= 2;
      sn -= 2;
    }
  }
  if(k){
    if(zero.size()){
      ans = 0;
    }
    else{
      ans = 1;
      for(int i = 0;i < K;i++){
	ans = ((ans)*(li[i].first*li[i].second)%mod+mod)%mod;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 9360
#pragma GCC optimize("O3")

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout cout << fixed << setprecision(15)

//typedef===============
typedef long long       ll;
typedef long double     ld;
typedef pair<int, int>  Pii;
typedef pair<ll, ll>    Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define eb emplace_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (n); ++(i))
#define reps(i, n)       for(int i = 1; (i) <= (n); ++(i))
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; --(i))
#define CtoI(c)         int((c)) - int('0')
#define ItoC(c)         char((c) + '0')

//functions=============
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };

/*--------additional--------*/



/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    char c; cin >> c;
    int ans = CtoI(c) + 1;
    cout << ItoC(ans) << endl;

return 0;
}

Measured memory_bytes: 3608
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
import java.math.BigDecimal;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	Main(BufferedReader in) throws IOException {
		String S = in.readLine();
		boolean result = false;
		if (S.length() % 2 != 0) {
			// 違う
		} else {
			int count = S.length() / 2;
			StringBuilder strBuilder = new StringBuilder();
			for(int i = 0; i < count; ++i) {
				strBuilder.append("hi");
			}
			String str = strBuilder.toString();
			if(S.equals(str)) {
				result = true;
			}
		}
		System.out.println((result ? "Yes" : "No"));
	}

	void calc() {
	}

	void showResult() {
	}

}


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

using namespace std;

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

    vector<int> a(N, 0);
    vector<int> b(N, 0);
    int M = 0;

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

    for (int i = N - 1; i >= 0; i--) {
        int sum = 0;
        // for (int j = 2 * (i + 1); j < N; j = j + (i + 1)) {
        for (int j = (i+1); i+j < N; j = j + (i + 1)) {
            sum += b[i+j];
        }

        sum %= 2;

        if (sum == a[i]) {
            b[i] = 0;
        } else {
            b[i] = 1;
            M++;
        }
    }

    cout << M << endl;

    for (int i = 0; i < N; i++) {
        if (b[i] == 1) {
            cout << i + 1 << " ";
        }
    }

    cout << endl;

    return 0;
}


Measured memory_bytes: 2432
object Main extends App {
  val Seq(r, c) = readLine.split(' ').map(_.toInt).toList

  val tab = for { i <- 0 until r} yield {
    val row = readLine.split(' ').map(_.toInt).take(c)
    row :+ row.sum
  }

  for (a <- tab :+ tab.reduce(_.zip(_).map(t=>t._1 + t._2))) {
    println(a.head.toString + a.tail.map(" %d".format(_)).reduce(_+_))
  }
}


Measured memory_bytes: 75264
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {
    public int solve(int W, List<Integer> weights, List<Integer> values) {
        int N = values.size();
        int[] dp = new int[W + 1];
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= W; ++j) {
                int w = weights.get(i - 1);
                if (j >= w) {
                    dp[j] = Math.max(dp[j], dp[j - w] + values.get(i - 1));
                }
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> weights = new ArrayList<>();
        List<Integer> values = new ArrayList<>();
        List<Integer> NW = Stream.of(scanner.nextLine().split("\\s")).map(Integer::valueOf)
                                      .collect(Collectors.toList());
        final int N = NW.get(0);
        final int W = NW.get(1);
        for (int i = 0; i < N; ++i) {
            List<Integer> collect = Stream.of(scanner.nextLine().split("\\s")).map(Integer::valueOf)
                                          .collect(Collectors.toList());
            values.add(collect.get(0));
            weights.add(collect.get(1));
        }
        System.out.println(new Main().solve(W, weights, values));
    }
}

Measured memory_bytes: 33084
#include<stdio.h>
int main(void)
{
	int a,x[101]={0},i;
	for(i=0; i<3; i++)
	{
		scanf("%d", &a);
		x[a]=1;
	}
	a=0;
	for(i=1; i<=100; i++)
	{
		if(x[i]>0)
		a++;
	}
	printf("%d\n", a);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,a) for(int i=0;i<(a);i++)
#define MOD 1000000007

int main(){
  while(1){
    string s; getline(cin, s);
    if(s==".") break;
    stack<char> st;
    bool flag=1;
    rep(i,s.length()){
      if(s[i]=='(') st.push('(');
      if(s[i]=='[') st.push('[');
      if(s[i]==')'){
        if(st.empty()) flag=0;
        else if(st.top()=='(') st.pop();
        else flag=0;
      }
      if(s[i]==']'){
        if(st.empty()) flag=0;
        else if(st.top()=='[') st.pop();
        else flag=0;
      }
    }
    if(flag and st.empty()) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
  }
  return 0;
}



Measured memory_bytes: 3240
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll n; cin>>n;
	ll val=7%n, mult=1;
	for (int i=1; i<=2e6; i++) {
		if(val==0) {
			cout<<i<<"\n";
			return 0;
		}
		mult=(mult*10)%n;
		val=(val+7*mult)%n;
	}
	cout<<-1<<"\n";
	return 0;
}

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

"""abc079_b"""

import sys
import pprint
import re

import itertools
pp = pprint.PrettyPrinter(indent=2)

def main():
    """Main function."""
    n = int(input())

    l = [2,1]

    if n == 1:
        print(l[1])
    else:
        for i in range(2,n+1):
            l.append(l[-2]+l[-1])
        print(l[-1])


if __name__ == '__main__':
    sys.exit(main())

Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
using namespace std;

int n,m,q;
int a[50],b[50],c[50],d[50];
int A[10];
int maxSum;

void dfs(int dep, int x){
    if(dep==n){
        int tmp=0;
        REP(int,i,0,q) if(A[b[i]]-A[a[i]]==c[i]) tmp+=d[i];
        if(maxSum<tmp) maxSum=tmp;
        return;
    }

    REP(int,i,x,m+1){
        A[dep]=i;
        dfs(dep+1,i);
    }
}

int main(){
    cin >> n >> m >> q;
    REP(int,i,0,q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--; b[i]--;
    }
  
  	maxSum=-1;
    dfs(0,1);
    cout << maxSum << endl;
    return 0;
}


Measured memory_bytes: 3632
N = int(input())
A = [int(x) for x in input().split(' ')]
all_s = 0
for x in A:
    all_s += x

half_size = all_s / 2.

acc = 0
for x in A:
    prev = acc
    acc += x
    if acc == half_size:
        print(0)
        break
    if acc > half_size:
        s1 = all_s - 2 * prev
        s2 = 2 * acc - all_s
        print(min(s1,s2))
        break

Measured memory_bytes: 26396
#include <stdio.h>

int is_prime(int n) {
    if (n == 1) return 0;

    for (int i = 2; i < (n + 1) / 2; i++) {
        if (n % i == 0) return 0;
    }

    return 1;
}


int main(int argc, char *argv[]) {
    int n;

    scanf("%d", &n);

    for (int i = 31; i <= 55555; i += 5) {
        if (is_prime(i)) {
            printf("%s%d", i == 31 ? "" : " ", i);
            if (--n == 0) break;
        }
    }

    printf("\n");

    return 0;
}

Measured memory_bytes: 128
N = input()
L = len(N)

C = [sum(list(map(int,N)))]

for i in range(1,L):
    if N[-1-i] != '0':
        c = N[:-1-i]+str(int(N[-1-i])-1)+str(9)*i
        C.append(sum(list(map(int,c))))
        
print(max(C))

Measured memory_bytes: 3316
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n:usize = read();
    let mut arr:Vec<u64> = (0..n).map(|_| read()).collect();
    arr.sort();
    arr.reverse();
    let mut ans = 0.0;
    for i in 0..n {
        let tmp = arr.pop().unwrap() as f64;
        if i == 0 {
            ans = tmp;
        } else {
            ans = (ans + tmp) / 2.0;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

X = list(map(int, input().split()))
sx=sum(X)
sx=sx*sx
sx%=mod
for x in X:
    sx -= x**2
    sx %= mod
print(div2(sx,2))


Measured memory_bytes: 94040
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1000000000 + 7;

bool debug = 0;

void solve() {
    int n;
    cin >> n;
    string s;
    int alpha = 26;
    vector<int> a(alpha, INT_MAX);
    for (int i = 0; i < n; i++) {
        vector<int> tmp(alpha, 0);
        cin >> s;
        for (int j = 0; j < (int)s.size(); j++) {
            tmp[(int)(s[j] - 'a')]++;
        }
        for (int j = 0; j < alpha; j++) {
            a[j] = min(a[j], tmp[j]);
        }
    }
    for (int i = 0; i < alpha; i++) {
        for (int j = 0; j < a[i]; j++) {
            cout << (char)('a' + i);
        }
    }
    cout << endl;
}

int main() {
    if (debug) {
        while (true) {
            cout << "********" << endl;
            solve();
        }
    } else {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll a[42],b[42],c[42],dp[42][401][401];
int main() {
	ll n,m1,m2;
	cin>>n>>m1>>m2;
	for(ll i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	ll ans=INF;
	for(ll i=0;i<=400;i++){
		for(ll j=0;j<=400;j++){
			for(ll k=0;k<n;k++){
				dp[k][i][j]=-1;
			}
		}
	}
	dp[0][0][0]=0;
	for(ll i=0;i<=400;i++){
		for(ll j=0;j<=400;j++){
			for(ll k=0;k<n;k++){
				if(dp[k][i][j]==-1){
					continue;
				}
				ll A=a[k],B=b[k],C=c[k];
				dp[k+1][i+A][j+B]=min(dp[k][i][j]+C,dp[k+1][i+A][j+B]);
				if(dp[k+1][i+A][j+B]=-1){
					dp[k+1][i+A][j+B]=dp[k][i][j]+C;
				}
				if((i+A)*m2==(j+B)*m1){
					ans=min(ans,dp[k+1][i+A][j+B]);
					//cout << ans<<" "<<k<<" "<< i+A<< " "<<j+B<< endl;
				}
				dp[k+1][i][j]=min(dp[k][i][j],dp[k+1][i][j]);
				if(dp[k+1][i][j]==-1){
					dp[k+1][i][j]=dp[k][i][j];
				}
			}
		}
	}
	cout <<(ans==INF?-1:ans);
	// your code goes here
	return 0;
}

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

int main()
{
  int a,b;
  cin >> a >> b;
  
  int sta = b - a;
  int sum = 0;
  for(int i = 1; i <= sta; i++){
    sum += i;
  }
  
  cout << sum - b << endl;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
using Graph = vector< vector<int> >;

vector<int> dist;
vector<bool> seen;

void solve_dist(Graph& g, int n, int x) {
    dist.assign(n, 0);
    seen.assign(n, false);
    
    queue<int> que;
    que.push(x);

    int ret = 0;
    while(!que.empty()) {
        int s = que.front();
        que.pop();
        if(seen[s]) continue;
        seen[s] = true;
        // cout << "ret " << ret++ << endl;
        // cout << "s = " << s << endl;
        for(auto v : g[s]) {
            if(dist[v] > 0) continue;
            dist[v] = dist[s] + 1;
            que.push(v);
            // cout << "x = " << x << ", v = " << v << endl;
        }
    }
}

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    x--; y--;

    Graph g(n);
    for(int i = 0; i < n - 1; i++) {
        g[i].push_back(i + 1);
        g[i + 1].push_back(i);
    }
    g[x].push_back(y);
    g[y].push_back(x);

    vector<int> ans(n, 0);
    for(int i = 0; i < n - 1; i++) {
        solve_dist(g, n, i);
        // for(int i = 0; i < n; i++) {
        //     cout << dist[i] << endl;
        // }
        for(int j = i + 1; j < n; j++) {
            ans[dist[j]]++;
        }
    }

    for(int i = 1; i < n; i++) cout << ans[i] << endl;
    
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

#define MAX 2000000
#define INFTY (1<<30)

int H, A[MAX+1];

void maxHeapify(int i){
  int l, r, largest,t;
  l = 2 * i;
  r = 2 * i + 1;

  //左の子、自分、右の子で値が最大のノードを選ぶ
  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r;

  if(largest != i){
    t = A[i];
    A[i] = A[largest];
    A[largest] = t;
    maxHeapify(largest);
  }
}

int extract(){
  int maxv;
  if(H < 1) return -INFTY;
  maxv = A[1];
  A[1] = A[H--];
  maxHeapify(1);
  return maxv;
}

void increaseKey(int i, int key){
  if(key < A[i]) return;
  int t;
  A[i] = key;
  while(i > 1 && A[i / 2] < A[i]){
    t = A[i];
    A[i] = A[i / 2];
    A[i / 2] = t;
    i /= 2;
  }
}

void insert(int key){
  H++;
  A[H] = -INFTY;
  increaseKey(H, key);
}

int main(){
  int key;
  char com[10];

  while(1){
    scanf("%s",com);
    if(com[0] == 'e' && com[1] == 'n') break;
    if(com[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }else printf("%d\n",extract());
  }
  
  return 0;
}



Measured memory_bytes: 5604
s=input()
a=int(s[:2])
b=int(s[2:])
if(a==0 or a>12):
    if(b==0 or b>12):
        print("NA")
    else:
        print("YYMM")
else:
    if(b==0 or b>12):
        print("MMYY")
    else:
        print("AMBIGUOUS")

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

int main() {
  int K, S;
  cin >> K >> S;
  int cnt = 0;
  for (int i = 0; i <= K; i++) {
    for (int j = 0; j <= K; j++) {
      int k = S - i - j;
      if (0 <= k and k <= K) cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}


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

using namespace std;

/**templates**/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;

#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sf(x) scanf("%lf",&x)
#define ss(x) scanf(" %s",x)
#define sc(x) scanf(" %c",&x)
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define aa first
#define bb second
#define sz(x) (ll)(x).size()
#define cas printf("Case %lld: ",++t)
#define casline printf("Case %lld:\n",++t)
//#define cas cout<<"Case "<<++t<<": "
//#define casline cout<<"Case "<<++t<<":"<<endl;
#define distance(x1,y1,x2,y2)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
#define endl "\n"
#define bug cout<<"bugggggggggggg "<<endl;
#define fast ios_base::sync_with_stdio(0);cin.tie(nullptr); ///no printf/scanf

const ll mod = 1000000007;
const ll inf = 1LL<<62;
const ll mx = 100005;
const double eps = 1e-10;

ll dx[10]={1,0,-1,0};
ll dy[10]={0,-1,0,1};

ll power(ll a,ll b)
{
    if(b==0)return 1;
    ll x=power(a,b/2);
    x=x*x;
    if(b%2)x=x*a;
    return x;
}

ll Set(ll N,ll pos){return N=N | (1LL<<pos);}
ll reset(ll N,ll pos){return N= N & ~(1LL<<pos);}
bool check(ll N,ll pos){return (bool)(N & (1LL<<pos));}

/**
double cosine_rule(double a,double b,double c)
{
    double res=(a*a+b*b-c*c)/(2*a*b);
    res=acos(res);
    return res;
}
*/

ll arr[mx],pre[mx],post[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    fast; ///no printf/scanf
    ll tst,a,b,c,k,n,m,res=0,ans=0,t=0;
    sl(n);
    for(ll i=1;i<=n;i++)
    {
        sl(arr[i]);
        pre[i]=__gcd(pre[i-1],arr[i]);
    }
    for(ll i=n;i>0;i--)
    {
        post[i]=__gcd(post[i+1],arr[i]);
    }
    for(ll i=1;i<=n;i++)
    {
        res=max(res,(__gcd(pre[i-1],post[i+1])));
    }
    cout<<res<<endl;


    return 0;
}


Measured memory_bytes: 2560
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string>


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

  std::string s;
  std::cin >> s;
  std::sort(std::begin(s), std::end(s));
  auto result = std::cend(s) == std::unique(std::begin(s), std::end(s));
  std::cout << (result ? "yes" : "no") << std::endl;

  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int odd[100000], even[100000];
int main(void) {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    if (i % 2) {
      cin >> odd[i / 2];
    } else {
      cin >> even[i / 2];
    }
  }
  if (n % 2 == 0) {
    for (int i = n / 2 - 1; i >= 0; i--) {
      cout << odd[i] << " ";
    }
    for (int i = 0; i < n / 2; i++) {
      cout << even[i] << " ";
    }
  } else {
    for (int i = n / 2; i >= 0; i--) {
      cout << even[i] << " ";
    }
    for (int i = 0; i < n / 2; i++) {
      cout << odd[i] << " ";
    }
  }
  cout << endl;
  return 0;
}

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

int main() {

  int N;
  int ac=0;
  int wa=0;
  int tle=0;
  int re=0;
  
  cin>>N;
  string S;
  for (int i=0;i<N;i++){
    cin >>S;
   if(S=="AC"){
     ac=ac+1;
   }
    if(S=="WA"){
     wa=wa+1;
   }
       if(S=="TLE"){
     tle=tle+1;
   }   if(S=="RE"){
     re=re+1;
   }
  }
  cout<<"AC x "<<ac<<endl;
    cout<<"WA x "<<wa<<endl;
    cout<<"TLE x "<<tle<<endl;
    cout<<"RE x "<<re<<endl;
 return 0;
}

Measured memory_bytes: 3628
def submit():
    n, m, q = map(int, input().split())

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

    def pattern(curr):
        if len(curr) == n:
            t = 0
            for a, b, c, d in points:
                if curr[b] - curr[a] == c:
                    t += d
            return t
        else:
            curr_max = 0
            if curr:
                st = curr[-1]
                ed = m
            else:
                st = 1
                ed = m

            for nxt in range(st, ed + 1):
                p = pattern(curr + [nxt])
                if p > curr_max:
                    curr_max = p
            return curr_max

    print(pattern([]))


submit()


Measured memory_bytes: 9232
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pr pair<int,int>
#define mod 1000000007
#define endl "\n"
vector<int> g[100005],a;

int power(int a,int b,int m=mod)
{
	if(b==0)	return 1;
	if(b==1)	return a;
	int res=power(a,b/2,m);
	res=(res*res)%m;
	if(b&1)	res=(res*a)%m;
	return res;
}
int modinv(int a,int m=mod){ return power(a,m-2,m);}
int add(int a,int b,int m=mod){	return (a+b)%m;}
int sub(int a,int b,int m=mod){	return (a-b+m)%m;}
int mul(int a,int b,int m=mod){	return (a*b)%m;}

bool dfs(int u)
{
	for(auto v:g[u])
	{
		if(a[v]>=a[u])
		{
			//cout<<v<<" "<<u<<endl;
			return false;
		}
	}
	return true;
}

void solve()
{
	int n,m;
	cin>>n>>m;
	//cout<<n<<" "<<m<<endl;
	a=vector<int> (n);
	int x,y,cnt=0;
	for(int i=0;i<n;i++)
		cin>>a[i];
	//for(int i=0;i<n;i++)
	//	cout<<a[i]<<" ";
	//cout<<endl;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		x--;y--;
		//cout<<"x and y are  "<<x<<" "<<y<<endl;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i=0;i<n;i++)
	{
		cnt+=dfs(i);
		//if(dfs(i))
			//cout<<i+1<<endl;
	}
	cout<<cnt<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int t=1;//cin>>t;
	while(t--)	solve();
	return 0;
}

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

using namespace std;

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<lli, int> pi;

lli lcm(lli a, lli b) {return (a*b)/__gcd(a, b);}

int main()
{
    int n;
    cin >> n;
    map<int, int> mp;
    while(n--){
        int x;
        cin >> x;
        mp[x]++;
    }
    int ans = 0;
    for(auto x: mp){
        if(x.second >= x.first){
            ans += (x.second-x.first);
        }
        else ans += x.second;
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 4736
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int n, m;
bool b[10];
bool graph[10][10];
void input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		graph[b][a] = true;
		graph[a][b] = true;
	}
}
int dfs(int nn, int s) {
	if (nn == n)return 1;
	b[s] = true;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (graph[s][i] && !b[i])cnt += dfs(nn + 1, i);
	}
	b[s] = false;
	return cnt;
}
int main() {
	input();
	cout << dfs(1, 1) << endl;
	char c; cin >> c;
}

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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int n;
int get(int a){
  cout << a << endl;
  string z;
  cin >> z; 
  if(z[0] == 'V')exit(0);
  return (z[0] == 'M') ^ (a % 2);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n;
  int po = 0;
  int ko = n;
  int wp = get(po);
  while(po+1 != ko){
    int m = (po + ko) / 2;
    if(get(m) == wp){
      po = m;
    }else{
      ko = m;
    }
  }
}


Measured memory_bytes: 852
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;

#define ll long long
#define pii pair<int,int>
/**==Info==
*Program:4
*Problem:Symmetric Grid
*Date:2018-4-21
*Algorithm:kawatea's Solution
*Stats:AC*/

bool debug=false;

int n,m;
string s[15];
string ss[15];
int a[15],b[15];

void dfs2(int pos,bool mid){
	if(pos==m){
		puts("YES");
		exit(0);
	}
	if(b[pos]!=-1){
		dfs2(pos+1,mid);
		return;
	}
	for(int i=pos+1;i<m;i++){
		if(b[i]!=-1){
			continue;
		}
		int j;
		for(j=0;j<n;j++){
			if(s[j][pos]!=s[a[j]][i]) break;
		}
		
		
		if(j==n){
			b[pos]=i;
			b[i]=pos;
			dfs2(pos+1,mid);
			b[pos]=-1;
			b[i]=-1;
		}
	}
	
	if(!mid){
		int j;
		for(j=0;j<n;j++){
			if(s[j][pos]!=s[a[j]][pos]) break;
		}
		
		if(j==n){
			b[pos]=pos;
			dfs2(pos+1,true);
			b[pos]=-1;
		}
	}
}

void dfs(int pos,bool mid){
	if(pos==n){
		dfs2(0,!m%2);
		return;
	}
	if(a[pos]!=-1){
		dfs(pos+1,mid);
		return;
	}
	for(int i=pos+1;i<n;i++){
		if(a[i]!=-1){
			continue;
		}
		if(ss[i]!=ss[pos]){
			continue;
		}
		
		a[i]=pos;
		a[pos]=i;
		
		dfs(pos+1,mid);
		
		a[pos]=-1;
		a[i]=-1;
	}
	
	if(!mid){
		a[pos]=pos;
		dfs(pos+1,true);
		a[pos]=-1;
	}
}

int main(int argc,char* argv[]){
	
	
	
	scanf("%d%d",&n,&m);
	
	
	for(int i=0;i<n;i++){
		cin>>s[i];
		ss[i]=s[i];
		sort(ss[i].begin(),ss[i].end());
	}
	
	int t=time(0);
	memset(a,-1,sizeof(a));
	memset(b,-1,sizeof(b));
	
	dfs(0,!n%2);
	
	while(time(0)-t<=1){
		
	}
	puts("NO");
	
	//Atcoder is just a f***ing website
	return 0;
}



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

void solve()
{
    int h, w, k;
    cin >> h >> w >> k;
    string a[h];
    for(int i = 0; i < h; i++)
    {
        cin >> a[i];
    }
    int ans = 0;

    for(int mask = 0; mask<1<<(h+w); mask++)
    {
        int cnt = 0;
        for(int x=0; x<h; x++)
        {
            for(int y=0; y<w; y++)
            {
                if(a[x][y]!='#') continue;
                if(mask&((1<<x)|(1<<(h+y)))) continue;
                cnt++;
            }
        }
        if(cnt==k)
            ans++;
    }

    cout << ans << endl;
}


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


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int n,x;
  cin >> n >> x;
  int i;
  int xx = x;
  vector<int> a(101);
  int count = 0;
  for(i=0;i<n;i++) cin >> a[i];
  sort(a.begin(),a.begin()+n);
  for(i=0;i<n;i++){
    if(x>=a[i]){
      x -= a[i];
      count++;
    }
    else break;
  }
  int sum = 0;
  for(i=0;i<count;i++) sum += a[i];
  if(count == n){
    if(sum < xx) cout << count -1 << "\n";
    else cout << count << "\n";
  }
  else cout << count << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define MAX 3000005
#define mod 1000000007
lli a[MAX];
lli b[MAX];
long long binpow(long long a, long long b) {
    lli m = 1000000007;
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli N;
    cin>>N;
    lli ansz =  0;
    lli s = 0;
    map <pair <lli,lli> , lli > mp;
    bool flag = false;
    for(lli i = 0; i<N; i++){
        cin>>a[i]>>b[i];
        if((a[i] == 0) & (b[i] == 0)){
            ansz++;
            continue;
        }
        lli gc = __gcd(a[i],b[i]);
        
        gc = abs(gc);
        a[i]/= gc;
        b[i] /= gc;
        
        if(a[i]*b[i] < 0)
            mp[make_pair(-abs(a[i]), -abs(b[i]))]++;
        else{

            mp[make_pair(abs(a[i]), abs(b[i]))]++;
        }
    }
    pair <lli,lli> candi;
    lli ans = 1;
    for(auto i = mp.begin(); i != mp.end(); i++){
        lli a = (*i).first.first;
        lli b = (*i).first.second;
        //cout<<a<<" "<<b<<" "<<mp[make_pair(a,b)]<<endl;
        s = 0;
        if((*i).second == 0)
            continue;
        if(a == 0 || b == 0){
            if((a == 0) && (b == 1) && (mp[make_pair(1,0)] == 0)){
                    s += binpow(2,(*i).second);
                    s %= mod;
                    ans *=s;
                    ans %= mod;
            }
            else if(a == 1 && b == 0){
                s += binpow(2, mp[(*i).first]);
                s += binpow(2, mp[make_pair(0,1)]);
                s -=1;
                s %= mod;
                ans *=s;
                ans %= mod;
            }
        }
        else if(a < 0){
            if(mp[make_pair(abs(b),abs(a))] == 0){
                //cout<<"map: "<<mp[make_pair(abs(b),abs(a))]<<endl;
                s += binpow(2,mp[make_pair(-abs(a), -abs(b))]);
                s %= mod;
               ans *= s;
                ans %= mod;
               // cout<<s<<endl;
            }
        }
        else if(a > 0){
            s += binpow(2,mp[(*i).first]);
            s %= mod;
            s += binpow(2,mp[make_pair(-abs(b), -abs(a))]);
            s -=1;
            s %= mod;
            ans *= s;
            ans %= mod;
           // cout<<s<<endl;
        }
    }
    ans = ans -1;
    ans += ansz;
    ans += mod;
    ans %= mod;
    cout<<ans;
}

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

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> pii;

#define REP(a,b,c) for(ll (a)=(b);(a)<(c);(a)++)
#define PER(a,b,c) for(ll (a)=(b);(a)>=(c);(a)--)

ll R, S, P;

ll pt(char cmp, ll usr){
    if(cmp == 'r' && usr == 2){
        return P;
    }
    if(cmp == 's' && usr == 0){
        return R;
    }
    if(cmp == 'p' && usr == 1){
        return S;
    }
    return 0;
}

int main(){
    ll N, K;
    cin >> N >> K;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    vector<vector<ll>> memo(N+K,vector<ll>(3,0));

    REP(i,0,K){
        REP(j,0,3){
            memo[i+K][j]=pt(T[i], (ll)j);
        }
    }

    REP(i,K,N){
        REP(hist,0,3){
            REP(cur,0,3){
                if(hist==cur) continue;
                memo[i+K][cur]=max(memo[i+K][cur],memo[i][hist]+pt(T[i], (ll)cur));
            }
        }
    } 

    ll ret=0;
    REP(i,N,N+K){
        ll s =*max_element(memo[i].begin(),memo[i].end());
        ret+=s;
    }
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 10624
N, X = map(int, input().split())
if X == 1 or X == 2 * N - 1:
    print("No")
    exit()

A = [0] * (2*N-1)
D = [i+1 for i in range(2*N-1)]
if X == 2:
    A[N-2] = X
    A[N-1] = X - 1
else:
    A[N-2] = X
    A[N-1] = X + 1
    A[N] = X - 1
    D.remove(X)
    D.remove(X + 1)
    D.remove(X - 1)
    if N >= 3:
        A[N-3] = X - 2
        D.remove(X - 2)
    
for i in range(2 * N - 1):
    if A[i] == 0:
        A[i] = D.pop()
    
print("Yes")
for a in A:
    print(a)

Measured memory_bytes: 12568
# !入力
# グラフの構築
# クエリの入力
# Kからの各点のの距離をdfs
# クエリの処理
from collections import deque
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  edge[a-1].append((b-1,c))
  edge[b-1].append((a-1,c))
q,k=map(int,input().split())
dist=[0]*n
seen=[False]*n
todo=deque([k-1])
while todo:
  par=todo.pop()
  seen[par]=True
  for cld,cost in edge[par]:
    if dist[cld]==0:
      if seen[cld]==False:
        dist[cld]=dist[par]+cost
        seen[cld]=True
        todo.append(cld)

for i in range(q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])
  
  

Measured memory_bytes: 44380
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define rep(i, a, b) for (int i = (a); i < (b); i++)
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...) 0
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, x;
    cin >> n >> x;
    vector<ll> b(n), l(n), u(n);
    vector<pair<ll, int>> s(n);
    ll d = 0;
    for (int i = 0; i < n; i++) {
        cin >> b[i] >> l[i] >> u[i];
        d -= b[i] * l[i];
        s[i] = {b[i] * l[i] + (x - b[i]) * u[i], i};
    }
    sort(s.rbegin(), s.rend());
    vector<ll> v(n);
    for (int i = 0; i < n; i++) {
        v[i] += s[i].first;
        if (i) v[i] += v[i - 1];
    }
    debug(s, v);
    ll lb = -1, ub = x * n;
    while (ub - lb > 1) {
        ll t = (ub + lb) / 2;
        ll q = t / x;
        ll r = t % x;
        ll sum = 0;
        if (q) sum += v[q - 1];
        ll tmp = 0;
        for (int i = q; i < n; i++) {
            int j = s[i].second;
            ll ss = 0;
            if (r <= b[j]) {
                ss = r * l[j];
            } else {
                ss = b[j] * l[j] + (r - b[j]) * u[j];
            }
            tmp = max(tmp, ss);
        }
        sum += tmp;
        tmp = 0;
        for (int i = 0; i < q; i++) {
            int j = s[i].second;
            ll ss = v[q] - s[i].first;
            if (r <= b[j]) {
                ss += r * l[j];
            } else {
                ss += b[j] * l[j] + (r - b[j]) * u[j];
            }
            tmp = max(tmp, ss);
        }
        sum = max(sum, tmp);
        if (sum + d < 0)
            lb = t;
        else
            ub = t;
    }
    cout << ub << endl;
    return 0;
}

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

using namespace std;

int main(){
  long n;
  cin >> n;
  long min = n-1;
  long move;
  for(int i=2;i<=sqrt(n);i++){
    if(n%i==0) {
      move = i-1 + n/i-1;
      if(min>move) min = move;
    }
  }
  cout << min;
  return 0;
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

main :: IO ()
main = do
    [a, b, c] <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine :: IO [Int]
    putStrLn $ if b - a == c - b then "YES" else "NO"


Measured memory_bytes: 380
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n' <- getInt
    as' <- getIntList
    let (o,as) = partition (== 1) as'
    let lo = length o
    let n = length as
    let ps = concatMap factorize as
    let vec = VU.create $ do
            v <- VUM.replicate 1000001 (0 :: Int)
            forM_ ps $ \i -> do
                VUM.modify v succ i
            return v
    let pmax = VU.maximum $ VU.drop 2 vec
    let ans | n == 0 = "pairwise coprime"
            | pmax == 1 = "pairwise coprime"
            | pmax /= n = "setwise coprime"
            | lo /= 0 = "setwise coprime"
            | otherwise = "not coprime"
    putStrLn ans

f n k
  | n < k = n
  | n `mod` k == 0 = f (n `div` k) k
  | otherwise = f (n `mod` k) k
 
primes = map fromIntegral primes'
  where
    primes' = [2, 3, 5] ++ f 5 7 (drop 2 primes')
    f m s (p:ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
      where
        ns = [x + y | x <- [s,s + 6 .. p * p - 2], y <- [0, 4]]

factorize 1 = [1]
factorize n = format $ factorize' n primes
  where
    format ps = map head $ group ps
    factorize' n ps@(p:ps')
      | p * p > n = [n]
      | rem n p == 0 = p : factorize' (div n p) ps
      | otherwise = factorize' n ps'

Measured memory_bytes: 99824
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define INF (1e9)

int D = 365;
vi c, ans;
vvi s;

void input() {
  cin >> D;
  c = vi(26);
  s = vvi(D, vi(26));
  for (int i = 0; i < 26; i++) {
    cin >> c[i];
  }
  for (int i = 0; i < D; i++) {
    for (int j = 0; j < 26; j++) {
      cin >> s[i][j];
    }
  }
}

void output() {
  for (int i = 0; i < D; i++) {
    cout << ans[i] + 1 << endl;
  }
}

int simulate(vi a) {
  int sum = 0;
  vi last(26, 0);
  for (int i = 0; i < D; i++) {
    sum += s[i][a[i]];
    last[a[i]] = i + 1;
    for (int j = 0; j < 26; j++) {
      sum -= c[j] * (i - last[j] + 1);
    }
  }
  return (int)1e6 + sum;
  // return max((int)1e6 + sum, 0);
}

void solve() {
  int best = simulate(ans);

  // 周期
  for (int i = 0; i < 26; i++) {
    vi a(D);
    for (int j = 0; j < D; j++) {
      a[j] = (i + j) % 26;
    }

    int x = simulate(a);
    if (x > best) {
      best = x;
      ans = a;
    }
  }

  //
  srand((unsigned)time(NULL));
  int loop = 20;
  bool lastIsNew = true;
  while (loop--) {
    vi a = ans;
    if (!lastIsNew) {
      int change = D / 5;
      while (change--) {
        a[rand() % D] = rand() % 26;
      }
    }

    for (int i = 0; i < D; i++) {
      vi b = a;
      int idx = 0, bst = simulate(b);
      for (int j = 0; j < 26; j++) {
        b[i] = j;
        int x = simulate(b);
        if (x > bst) {
          bst = x;
          idx = j;
        }
      }
      a[i] = idx;
    }

    lastIsNew = false;
    int x = simulate(a);
    if (x > best) {
      best = x;
      ans = a;
      lastIsNew = true;
    }
  }
}

int main() {
  input();
  ans = vi(D, 0);
  solve();
  output();
}


Measured memory_bytes: 3736
from collections import Counter


S = input()
C = Counter(S)
vs = sorted(list(C.values()))
if len(vs) == 1:
    print("YES") if vs[0] == 1 else print("NO")
elif len(vs) == 2:
    print("YES") if vs[0] == vs[1] and vs[0] == 1 else print("NO")
else:
    print("YES") if vs[2] - 1 <= vs[0] and vs[2] - 1 <= vs[1] else print("NO")


Measured memory_bytes: 3444
S = input()

if 1 <= int(S[2] + S[3]) <= 12 and 1 <= int(S[0] + S[1]) <= 12:
  print('AMBIGUOUS')
elif 1 <= int(S[2] + S[3]) <= 12 and not (1 <= int(S[0] + S[1]) <= 12):
  print('YYMM')
elif 1 <= int(S[0] + S[1]) <= 12 and not (1 <= int(S[2] + S[3]) <= 12):
  print('MMYY')
else:
  print('NA')

Measured memory_bytes: 3064
h, w = gets.chomp.split.map(&:to_i)
bord = []

h.times do
  bord << gets.chomp.split('')
end

count = bord.map{|line| line.count('.') }.inject(:+)
d = Array.new(h){Array.new(w, 0)}

d = bord.map{|line| line.map{|c| c == '#' ? -1 : 0}}
d[0][0] = 1
q = [[0, 0]]

q.each do |sy, sx|
  break if d[h-1][w-1] != 0
  [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dy, dx|
    x = sx + dx
    y = sy + dy
    if x >= 0 && y >= 0 && x < w && y < h && d[y][x] == 0
      q << [y, x]
      d[y][x] = d[sy][sx] + 1
    end
  end
end

puts d[h-1][w-1] == 0 ? -1 : count - d[h-1][w-1]

Measured memory_bytes: 3836
suit = ["S","H","C","D"]
num=[]

for i in range(1,14):
    num.append(i)

li=[]
for i in suit:
    for j in num:
        li.append(i+" "+str(j))

n=int(input())

for i in range(n):
    sn=str(input())
    if (sn in li):
        li.remove(sn)

for i in range(len(li)):
    print(li[i])
 


Measured memory_bytes: 5596
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }

vector<long long> enum_divisors(long long N) {
    vector<long long> res;
    for (long long i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            // 重複しないならば i の相方である N/i も push
            if (N/i != i) res.push_back(N/i);
        }
    }
    return res;
}

int main(){ 
  int n; cin >> n;
  vector<ll> A(n), cnt(1001000);
  vector<vector<ll>> yaku(n); 
  rep(i, n){
    cin >> A[i];
    yaku[i] = enum_divisors(A[i]);
    cnt[A[i]]++;
  }
  int res = 0;
  rep(i, n){
    if(cnt[A[i]]>1)continue;
    bool fg = true;
    for(auto num: yaku[i]){
      if(num==A[i])continue;
      //cout << "num: " << num << " mp:" << mp[num] << ln; 
      if(cnt[num]>0){fg = false; break;}
    }
    if(fg) res++;
  }

  cout << res << ln;
}



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

int main(){
  int N,K;
  int l[60];
  cin>>N>>K;
  for(int i=0;i<N;i++)cin>>l[i];
  sort(l,l+N);
  reverse(l,l+N);
  int ans=0;
  for(int i=0;i<K;i++)ans+=l[i];
  cout<<ans<<endl;
  return 0;

}


Measured memory_bytes: 256