akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
int int_max = 2147483647;
i64 INF = 1e16;
int max_n = 1e5;


int main(int argc, char **argv) {
    i64 n;
    cin >> n;

    vector<i64> as(n+1);
    i64 sum_a{0};
    for (int i=0; i<n+1; ++i) {
        cin >> as[i];
        sum_a += as[i];
    }

    if (n==0) {
        if (as[0]<2) cout << as[0] << endl;
        else cout << -1 << endl;
        return 0;
    }
    i64 ans{0}, level_nodes{1};

    for (int i=0; i<n+1; ++i) {
        sum_a -= as[i];

        if (as[i] > level_nodes) {
            cout << -1 << endl;
            return 0;
        }

        ans += level_nodes;

        if ((level_nodes-as[i]) < sum_a)
            level_nodes = min((level_nodes-as[i])*2, sum_a);
        else
            level_nodes = sum_a;
    }

    cout << ans << endl;

    return 0;
}


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

int main(){
    int n, m; cin >> n >> m;
    vector<int> lis1(10, 0), lis2(10,0), lis3(10, 0);
    for(int i = 0; i < m; i++){
        int s, c; cin >> s >> c;
        if(s == 1){
            lis1[c]++;
        }else if(s == 2){
            lis2[c]++;
        }else{
            lis3[c]++;
        }
    }
    if(n != 1){
        if(lis1[0] > 0){
            cout << -1 << endl;
            return 0;
        }
    }
    int f = 0, f1 = 0, f2 = 0;
    if(n == 1){
        for(int i = 0; i < 10; i++){
            if(lis1[i] > 0){
                f++;
            }
        }
        if(f > 1){
            cout << -1 << endl;
            return 0;
        }
        for(int i = 0; i < 10; i++){
            if(lis1[i] > 0){
                cout << i << endl;
                return 0;
            }
        }
        cout << 0;
        return 0;
    }
    else if(n == 2){
        for(int i = 0; i < 10; i++){
            if(lis1[i] > 0){
                f++;
            }
            if(lis2[i] > 0){
                f1++;
            }
        }
        if(f > 1 || f2 > 1){
            cout << -1 << endl;
            return 0;
        }
        for(int i = 0; i < 10; i++){
            if(lis1[i] > 0){
                cout << i;
            }
        }
        if(f == 0){
            cout << 1;
        }
        for(int i = 0; i < 10; i++){
            if(lis2[i] > 0){
                cout << i;
                return 0;
            }
        }
        if(f1 == 0){
            cout << 0;
        }
        return 0;
    }
    else{
        for(int i = 0; i < 10; i++){
            if(lis1[i] > 0){
                f++;
            }
            if(lis2[i] > 0){
                f1++;
            }
            if(lis3[i] > 0){
                f2++;
            }
        }
        if(f > 1 || f1 > 1 || f2 > 1){
            cout << -1 << endl;
            return 0;
        }
        for(int i = 0; i < 10; i++){
            if(lis1[i] > 0){
                cout << i;
            }
        }
        if(f == 0){
            cout << 1;
        }
        for(int i = 0; i < 10; i++){
            if(lis2[i] > 0){
                cout << i;
            }
        } 
        if(f1 == 0){
            cout << 0;
        }
        for(int i = 0; i < 10; i++){
            if(lis3[i] > 0){
                cout << i;
            }
        } 
        if(f2 == 0){
            cout << 0;
        }
        return 0;
    }
}

Measured memory_bytes: 256
<?php
    while( true ) {
        fscanf( STDIN, "%d%d", $H, $W );
        if( 0 == $H && 0 == $W ) { break; }
         
        $buf = array();
		if( 1 < $H && 1 < $W ) {
			array_push( $buf, str_repeat( '#' , $W ) );
	        for( $i=0; $i<$H-2; $i++ ) {
				array_push( $buf, '#'.str_repeat( '.' , $W-2 ).'#' );
	        }
			array_push( $buf, str_repeat( '#' , $W ) );
		} else {
			array_push( $buf, '#' );
		}
        print implode( "\n", $buf ).PHP_EOL.PHP_EOL;
    }
	return;
?>

Measured memory_bytes: 6708
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
int n,ans[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i*i<=n;i++)
	for(int j=1;j*j<=n;j++)
	for(int k=1;k*k<=n;k++)
	if(i*i+j*j+k*k+i*j+j*k+k*i<=n)ans[i*i+j*j+k*k+i*j+j*k+k*i]++;
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}

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

int main() {
    string s;
    cin >> s;
    for(int i=0; i<=3; i++) cout << s[i];
    cout << " ";
    for(int i=4; i<=11; i++) cout << s[i];
    cout << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

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

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}
template<typename T>
T lcm( T m, T n )
{
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    long long N;
    long long ans=1<<30;
    cin >> N;
    vector<long long>a(N);

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

    for(int i=-101; i<101; i++){
        long long cost=0;
        for(int j=0; j<N; j++){
            cost+=(i-a[j])*(i-a[j]);
        }
        ans=min(cost,ans);
    }

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



Measured memory_bytes: 256
"""
案件を報酬を受け取るまでにかかる時間で降順ソートしておく。
"""
class segTree:
    def __init__(self,n,identity):
        if bin(n).count("1") == 1:
            self.leaves = 2**(n.bit_length()-1)
        else:
            self.leaves = 2**n.bit_length()
        self.identity = identity
        self.tree = [[self.identity,-1] for i in range(self.leaves*2)]
        for i in range(self.leaves,self.leaves*2):
            self.tree[i] = [self.identity,i-self.leaves]

    def merge(self,x,y):
        #ここにマージ処理を書く
        if x[0] < y[0]:
            return x[::1]
        else:
            return y[::1]

    def update(self,i,x):
        i = i+self.leaves
        self.tree[i][0] = x
        i >>= 1
        while i > 0:
            self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
            i >>= 1

    def query(self,l,r):
        #[l:r)のクエリ結果を返す
        l = l + self.leaves
        r = r + self.leaves
        res = [self.identity,-1]
        while l < r:
            if l&1:
                res = self.merge(res,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                res = self.merge(res,self.tree[r])
            l >>= 1
            r >>= 1
        return res

N,M = map(int,input().split())
M += 1
sgt = segTree(N,float("INF"))
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x: -x[0])

today = 1
for i in range(N):
    a,b = AB[i]
    due = M-a
    #M日までに報酬を受け取るためには、何日までに働かなくてはいけないかを求める。

    if today <= due:
        #今日の日付がdue以下であれば、今日その仕事をこなす
        sgt.update(today-1,b)
        today += 1
    else:
        if due < 1:
            continue
        #今日の日付がdueを過ぎてしまっている場合は、due以前の労働で報酬がb以下の仕事のうち、報酬がもっとも低い仕事を塗り替える。
        tmp = sgt.query(0,due)
        if tmp[0] < b:
            sgt.update(tmp[1],b)
        
ans = 0
for i in range(N):
    if sgt.tree[i+sgt.leaves][0] != float("INF"):
        ans += sgt.tree[i+sgt.leaves][0]
print(ans)




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

if(len(set(a)) <= k):
    print(0)
else:
    dic_a = {x:0 for x in set(a)}
    for i in a:
        dic_a[i] += 1
    sum = 0
    a = sorted(dic_a.values(),reverse=True)
    for i in range(k,len(a)):
        sum += a[i]
    print(sum)

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

int K[20][20];
int n,m,a,b,c,d;
int Floyd(int K[20][20],int n) {
	for(int k=0; k<n; ++k) {
		for(int i=0; i<n; ++i) {
			for(int j=0; j<n; ++j) {
				if(K[i][j] > K[i][k] + K[k][j]) {
					K[i][j] = K[i][k] + K[k][j];
				}
			}
		}
	}
	return 0;
}

int main() {
	scanf("%d\n",&n);
	scanf("%d\n",&m);
	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			K[i][j] = 100000;
		}
	}
	for(int i=0; i<m; ++i) {
		scanf("%d,%d,%d,%d\n",&a,&b,&c,&d);
		K[a-1][b-1] = c;
		K[b-1][a-1] = d;
	}
	scanf("%d,%d,%d,%d",&a,&b,&c,&d);
	Floyd(K,n);
	cout << c-d-K[a-1][b-1]-K[b-1][a-1] << endl;
}

Measured memory_bytes: 1212
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int M = sc.nextInt();
		if (N == 1) {
			System.out.println(1);
			return;
		}
		boolean[] date = new boolean[N+1];
		for (int i = 0; i < M; i++) {
			int broken = sc.nextInt();
			date[broken] = true;
		}
		long beforeL = 1;
		long last = 1;
		if (date[1]) {
			last = 0;
		}
		for (int i = 2; i <= N; i++) {
			if (date[i]) {
				beforeL = last;
				last = 0;
			} else {
				long temp = last;
				last += beforeL;
				last %= 1000000007;
				beforeL = temp;
			}
		}
		long ans = last;
		System.out.println(ans);
	}

}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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

Measured memory_bytes: 22436
#include <iostream>

int main(){
    int k, s;
    std::cin >> k >> s;

    int count = 0;
    for (int i = 0; i <= k; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            if ((s - i - j <= k) && (i + j <= s))
            {
                count++;
            }
        }
    }
    
    std::cout << count << std::endl;

    return 0;
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n; cin >> n;
  vector<ll> a(n),b(n);
  for(int i = 0; i < n; ++i)cin >> a[i] >> b[i];
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  if(n&1){
    cout << b[n>>1] - a[n>>1] + 1 << endl;
  } else {
    double l = (a[(n>>1)]+a[(n>>1)-1])/2.;
    double h = (b[(n>>1)]+b[(n>>1)-1])/2.;
    cout << ll((h - l)*2 + 1) << endl;
  }
  
  return 0;
}


Measured memory_bytes: 6364
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    bool ans=true;
    if(a==b && a!=c){

    }
    else if(a==c && a!=b){

    }
    else if(b==c && a!=b){

    }
    else{
        ans = false;
    }
    if(ans){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    int a,b,c,d,turn;
    cin>>a>>b>>c>>d;

    turn = 0;
    while(1){
        if(a<=0 || c<=0){
            break;
        }else{
            if(turn == 0){
                c -= b;
                turn =1;
            }
            else{
                a -=d;
                turn = 0;
            }
        }
    }
    if(turn == 0){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using Graph = vector<vector<int>>;
const int INF = 998244353;
bool palin(string S){//Sが回文かどうか
    int M = (S.size()-1)/2 + 1;
    int n = S.size();
    bool flag = true;
 
    for(int i = M;i<n;i++){
        if(S[i] != S[n-i-1]) flag = false;
    }
   return flag;
}

using Graph = vector<vector<int>>;
/*
*/


int main() {
   string s;
   cin >> s;
   ll ans = 0;
   int l = 0;//sの先頭
   int r = s.size()-1;//rの末尾
   while(l<r){
       if(s[l] == s[r]){
          l++;
          r--;
       }
       else if(s[l] == 'x' && s[r] != 'x'){
           l++;
           ans++;
       }
       else if(s[l] != 'x' && s[r] == 'x'){
           r--;
           ans++;
       }
       else if(s[l] != 'x' && s[r] != 'x'){
           ans = -1;
           break;
       }
   }
   cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
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;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
const long long MOD =1000000000+7;

int main()
{
	string w;
	cin >>w;
	int ans=1;
	map<char,int>data;
	for(int i=0;i<w.size();i++){
		data[w[i]]++;
	}
	for(auto itr=data.begin();itr!=data.end();itr++){
		if(itr->second%2==1){
			ans=0;
		}
	}
	cout <<(ans==1?"Yes":"No")<<endl;
	
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath> 
using namespace std;

int main(){
    string S;
    cin >> S;
    int w;
    cin >> w; 
    int len = 0;
    for(int i=0;S[i]!='\0';i++)
        len++;

    for(int i=0;i<len;i=i+w){
        cout << S[i];
    }
    cout << endl;
    return 0;
}

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

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

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	if (A >= 10 || B >= 10)cout << -1;
	else cout << A * B;
}

Measured memory_bytes: 256
N, A, B, C, D = map(int, input().split())
S = input()
S = "#" + S + "#"

# A -= 1
# B -= 1
# C -= 1
# D -= 1

def can_reach(start, end):
    for i in range(start, end + 1):
        if S[i] == '#' and S[i + 1] == '#':
            return False
    return True


if not can_reach(A, C) or not can_reach(B, D):
    print("No")
    exit()

if C > D:
    cover = False
    for i in range(B, D + 1):
        if S[i - 1] == '.' and S[i] == '.' and S[i + 1] == '.':
            cover = True
    if not cover:
        print("No")
        exit()


print("Yes")

Measured memory_bytes: 41456
package main

import "fmt"

func main() {
	n := make([]int, 2)
	for i := 0; i < 2; i++ {
		fmt.Scan(&n[i])
	}
	if contains(n, 1) == false {
		fmt.Println(1)
	}
	if contains(n, 2) == false {
		fmt.Println(2)
	}
	if contains(n, 3) == false {
		fmt.Println(3)
	}
}

func contains(s []int, e int) bool {
	for _, v := range s {
		if e == v {
			return true
		}
	}
	return false
}


Measured memory_bytes: 512
n,m = map(int,input().split())
s=[]
c=[]
# ans = []
for i in range(m):
    si,ci = map(int,input().split())
    s.append(si)
    c.append(ci)

# for i in range(n):
#     ans.append(0)
    
# chk = ans[:]

# for i,v in enumerate(s):
#     ans[v-1] = c[i]

# if len(ans) != 1 and ans[0] == 0:
#     print(-1)
#     exit()

# for i, v in enumerate(s):
#     if ans[v-1] == c[i]:
#         chk[v-1] = 0
#     else:
#         chk[v-1] = 1
    
    
# if 1 in chk:
#     print(-1)
#     exit()


# cnt = len(ans)
# ans2 = 0
# if cnt == 1:
#     print(ans[0])
#     exit()
# elif cnt == 2:
#     ans2 = 10 * ans[0] + ans[1]
#     print(ans2)
#     exit()
# elif cnt == 3:
#     ans2 = 100 * ans[0] + 10 * ans[1] + ans[2]
#     print(ans2)
#     exit()
keta = 0
start = 0
if n == 1:
    keta = 10
    start = 0
elif n == 2:
    keta = 100
    start = 10
elif n == 3:
    keta = 1000
    start = 100
    
def chk_num(num):
    num = str(num)
    flg = 0
    for i,v in enumerate(s):
        if num[v-1] != str(c[i]):
            flg = 1
            break
    return flg
    

for i in range(start,keta):
    if chk_num(i) == 0:
        print(i)
        exit()

print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
Int INF = 1e18;
double EPS = 0.00000001;
//Int mod = 1e6+3;

int main() {
    Int n, c;
    cin >> n >> c;
    vector<Int> x(n), v(n);
    for (Int i = 0; i < n; i++) cin >> x[i] >> v[i];
    vector<Int> a(n + 1, 0), b(n + 1, 0);
    for (Int i = 0; i < n; i++) a[i + 1] += a[i] + v[i];
    for (Int i = 0; i < n; i++) b[i + 1] += b[i] + v[i];
    for (Int i = 1; i <= n; i++) a[i] -= x[i - 1];
    for (Int i = 0; i < n; i++) a[i + 1] = max(a[i + 1], a[i]);
    Int res = 0;
    for (Int i = 0; i < n; i++) {
        // B が x[i] のときの最大を O(1) で求めたい
        Int ma = b[n] - b[i] - (c - x[i]);
        ma += max((Int)0, a[i] - (c - x[i]));
        res = max(res, ma);
    }
    vector<Int> xr(n), vr(n);
    for (Int i = 0; i < n; i++) {
        xr[i] = c - x[n - 1 - i];
        vr[i] = v[n - 1 - i];
    }
    vector<Int> ar(n + 1, 0), br(n + 1, 0);
    for (Int i = 0; i < n; i++) ar[i + 1] += ar[i] + vr[i];
    for (Int i = 0; i < n; i++) br[i + 1] += br[i] + vr[i];
    for (Int i = 1; i <= n; i++) ar[i] -= xr[i - 1];
    for (Int i = 0; i < n; i++) ar[i + 1] = max(ar[i + 1], ar[i]);
    for (Int i = 0; i < n; i++) {
        Int ma = br[n] - br[i] - (c - xr[i]);
        //if (ar[i] == 0) ma += c - xr[i];
        ma += max((Int)0, ar[i] - (c - xr[i]));
        res = max(res, ma);
    }
    dump(res);
    return 0;
}

Measured memory_bytes: 6528
package main

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

type Shop struct {
	price  int64
	amount int64
}

type Shops []Shop

func (s Shops) Len() int {
	return len(s)
}

func (s Shops) Less(a, b int) bool {
	return s[a].price < s[b].price
}

func (s Shops) Swap(a, b int) {
	s[a], s[b] = s[b], s[a]
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nShops := scanInt(sc)
	nDesired := scanInt(sc)

	shops := make([]Shop, nShops)
	for i := 0; i < nShops; i++ {
		shops[i] = Shop{
			price:  int64(scanInt(sc)),
			amount: int64(scanInt(sc)),
		}
	}

	sort.Sort(Shops(shops))

	money := int64(0)
	nRest := int64(nDesired)
	for _, shop := range shops {
		nBought := min(nRest, shop.amount)
		money += shop.price * nBought
		nRest -= nBought
		if nRest == 0 {
			break
		}
	}

	fmt.Println(money)
}

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

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}


Measured memory_bytes: 3840
#include <iostream>
#include <string>
#include <vector>

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

using namespace std;

int main(void){

    //input
    int N;
    cin >> N;

    //output
    string ans = "No";

    int N1 = N % 10;
    if( (N1 % 7) == 0 && (N1 != 0)) ans = "Yes";

    N = N / 10;
    int N10 = N % 10;
    if(N10 % 7 == 0 && (N10 != 0)) ans = "Yes";

    N = N / 10;
    int N100 = N % 10;
    if(N100 % 7 == 0 && (N100 != 0)) ans = "Yes";
        
    cout << ans;

    return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;

int main(){
  int n,w;
  while(cin>>n>>w && n){
    int cnt[20] = {};
    int item = 2;
    int height = 0;
    REP(i,n){
      int t; cin>>t;
      cnt[t/w]++;
      height = max(height, cnt[t/w]);
      item = max(item, t/w+1);
    }
    double ans = 0.01;
    REP(i,item){
      double x = 1.0 - (double)i/(item-1);
      x *= (double)cnt[i]/height;
      ans += x;
    }
    printf("%.6lf\n",ans);
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
 ll a,b,c,k; cin>>a>>b>>c>>k;
 ll n=k;
 ll res=0;
	if(a>k)
	{
		cout<<k; return 0;
	}
	if(a<=k)
	{
		res+=a;
		k-=a;
	}
	if(k>0)
	{
		if(b>0)
		{
			k-=b;
		}
	}
	if(k>0)
	{
		res=res+(k*-1);
		
	}
	cout<<res;
	
}

Measured memory_bytes: 3636
while True:
    a,b = map(int,input().split())
    if a==0 and b==0:
        break
    c = 0
    for i in range(1,a+1):
        for j in range(i+1,a+1):
            for k in range(j+1,a+1):
                if i+j+k == b:
                    c+= 1
    print(c)


Measured memory_bytes: 5592
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;

int main(){
    fast_io

    ll n, p;
    cin>>n>>p;
    ll ans=1;
    
    for(ll i=2;i*i<=p;i++){
        int num=0;
        while(p%i==0){
            num++;
            p/=i;
        }
        int cnt=num/n;
        for(int j=0;j<cnt;j++) ans*=i;
    }
    if(n==1) ans*=p;
    cout<<ans<<endl;
    return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<int,P>
#define vpp vector<PP>
#define fi first
#define se second
#define INF 1e9
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
vi calc(int n){
    vi a(n);
    REP(i,n){
        a.back()++;
        if(i)a[i-1]--;
    }
    REPR(i,n-2){
        a[i]+=a[i+1];
    }
    REP(i,n){
        if(i)a[i-1]-=n-i;
    }
    REPR(i,n-2){
        a[i]+=a[i+1];
    }
    return a;
}
signed main(){
    int n,m;
    cin>>n>>m;
    vi a=calc(n-1);
    vi b=calc(m-1);
    int p=0;
    int now;
    cin>>now;
    REP(i,n-1){
        int t;
        cin>>t;
        (p+=(t-now)*a[i])%=MOD;
        now=t;
    }
    int q=0;
    cin>>now;
    REP(i,m-1){
        int t;
        cin>>t;
        (q+=(t-now)*b[i])%=MOD;
        now=t;
    }
    cout<<(p*q)%MOD<<endl;
    return 0;
}

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

using namespace std;

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

int main()
{
    int x;
    int n;
    int rcounter;
    int lcounter;
    rcounter = 0;
    lcounter = 0;

    cin >> x >> n;
    vector<int> v(n);

    rep(it, 0, n)
        cin >> v[it];

    if (n==0) {
        cout << x << "\n";
        return 0;
    }

    while (true) {
        if (find(v.begin(), v.end(), x+rcounter) != v.end()) {
            // in right
            rcounter++;
            if (find(v.begin(), v.end(), x-lcounter) != v.end()) {
                // in left
                lcounter++;
                continue;
            }
        } else {
            // not in right
            if (find(v.begin(), v.end(), x-lcounter) != v.end()) {
                // in left
                cout << x+rcounter << "\n";
                return 0;
            } else {
                cout << x-lcounter << "\n";
                return 0;
            }
        }
    }

    return 0;
}

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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int H,W;
const int N = 10;
int minCost [N] [N];
const int INF = 1e9;

int main()
{
	scanf("%d%d",&H,&W);
	FOR(i,0,N) FOR(j,0,N) scanf("%d",&minCost [i] [j]);

	FOR(k,0,N) FOR(i,0,N) FOR(j,0,N) chmin(minCost [i] [j],minCost [i] [k] + minCost [k] [j]);
	int ans = 0;
	FOR(i,0,H) FOR(j,0,W){
		int num;
		scanf("%d",&num);
		if(num == -1) continue;
		ans += minCost [num] [1];
	}
	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int N = sc.nextInt();

		int re = 0;
		for (int i = 1; i <= N; i += 2) {
			int count = 0;
			for (int k=1;k<=i;k++) {
				if(i%k==0) {
					count++;
				}
			}
			if(count == 8) {
				re++;
			}
		}
out.println(re);
		out.flush();

	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

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

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

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

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

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

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


Measured memory_bytes: 22740
#include "bits/stdc++.h"
using namespace std;

int main()
{
    unsigned long int N, A, B, R, S;
    cin >> N >> A >> B;

    S = A + B;
    R = (N / S) * A;
    R += (N % S) > A ? A : N % S;

    cout << R << endl;
}


Measured memory_bytes: 256
/**
 *    author:  Mohamad Milhem
**/

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define MOD ll(1000000007)
#define debug(x) cout << '[' << #x << " is: " << x << "] " <<endl;
#define decimalpoint cout << std::fixed << setprecision(5)


void solve(){
	long long D , T , S;
	cin >> D >> T >> S;

	if (S*T >= D){
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

}



int main()
{
    FAST;
    int t;
    t = 1;

    while(t--){
        solve();
    }
    return 0;
}


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

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll ;
typedef long double ld ;

const ll MOD = 1E9 + 7, INF = 2E18 + 5 ;
const double PI = 2 * acos(0.0) ;
const long double EPS = 1.0E-14 ;

int main()
{
    ll x, ans = 0 ;
    for (int i = 1; i <= 5; i++) {
        cin >> x ;
        if (x == 0) {
            ans = i ;
        }
    }
    cout << ans ;


    return 0 ;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
    using namespace std;
    typedef long long int ll;
    ll sum[1<<19],A[1<<19],pos[1<<19],dp[1<<19];
    int main()
    {
    	int n;
    	cin>>n>>pos[0];
    	for(int i=0;i<n;i++) cin>>A[i];
    	for(int i=0;i<n;i++)
    	{
    		pos[i+1]=min(pos[i],llabs(A[i]-pos[i]));
    	}
    	dp[n]=0;
    	for(int i=n-1;i>=0;i--)
    	{
    		dp[i]=dp[i+1];
    		if(A[i]/2LL<=dp[i]) dp[i]+=A[i];
    	}
    	int Q;
    	cin>>Q;
    	for(int i=0;i<Q;i++)
    	{
    		int t;
    		cin>>t;
    		t--;
    		if(pos[t]<=dp[t+1]) cout<<"NO";
    		else cout<<"YES";
    		cout<<'\n';
    	}
    	return 0;
    }


Measured memory_bytes: 14208
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<list>
#include <cstring>
#include <functional>
//#include<unordered_map>
//#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF ((Int)1<<60)
#define EPS (1e-10)
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long Int;
typedef pair<Int, Int> P; 
typedef vector<double> vec;
typedef vector<vec> mat;
const int N = 200005;
//////////////////////////////

Int fact[1100000];
Int revfact[1100000];
Int rev[1100000];

void init() {
	Int m = MOD;
	fact[0] = 1;
	revfact[0] = 1;
	rev[0] = 0;
	rev[1] = 1;
	for (Int i = 1; i < 1100000; i++) {
		fact[i] = fact[i - 1] * i % m;
		if (i>1)rev[i] = MOD / i * (MOD - rev[MOD % i]) % MOD;
		revfact[i] = revfact[i - 1] * rev[i] % MOD;
	}
}

Int nCk(Int n, Int k) {
	if (n < k)return 0;
	return fact[n] * revfact[n - k] % MOD * revfact[k] % MOD;
}

Int mod_pow(Int x, Int a, Int m = MOD) {
	if (a == 0)return 1;
	Int res = mod_pow(x, a / 2, m);
	res = res * res % m;
	if (a % 2)res *= x;
	return res % m;
}

Int inv(Int x, Int m = MOD) {
	return mod_pow(x, m - 2, m);
}

Int dp1[220000];
Int dp2[220000];
Int size1[220000];
Int size2[220000];
Int n, a, b;
vector<Int> edge[220000];
Int ans[220000];

void dfs1(Int x, Int last = -1) {
	size1[x] = 1;
	dp1[x] = 1;
	for (auto to : edge[x]) {
		if (to == last)continue;
		dfs1(to, x);
		size1[x] += size1[to];
		dp1[x] *= dp1[to]; dp1[x] %= MOD;
		dp1[x] *= revfact[size1[to]]; dp1[x] %= MOD;
	}
	size2[x] = n - size1[x];
	dp1[x] *= fact[size1[x] - 1]; dp1[x] %= MOD;
}

void dfs2(Int x, Int last = -1) {
	if (last == -1) dp2[x] = 1;
	Int all_product = dp2[x] * revfact[size2[x]] % MOD;
	for (auto to : edge[x]) {
		if (to == last)continue;
		all_product *= dp1[to]; all_product %= MOD;
		all_product *= revfact[size1[to]]; all_product %= MOD;
	}
	for (auto to : edge[x]) {
		if (to == last)continue;
		Int tmp = all_product;
		tmp *= inv(dp1[to]); tmp %= MOD;
		tmp *= inv(revfact[size1[to]]); tmp %= MOD;
		tmp *= fact[size2[to] - 1]; tmp %= MOD;
		dp2[to] = tmp;
		dfs2(to, x);
	}
}


void dfs3(Int x, Int last = -1) {
	if (last == -1)dp2[x] = 1;
	Int all_product = dp2[x] * revfact[size2[x]] % MOD;
	for (auto to : edge[x]) {
		if (to == last)continue;
		dfs3(to, x);
		all_product *= dp1[to]; all_product %= MOD;
		all_product *= revfact[size1[to]]; all_product %= MOD;
	}
	all_product *= fact[n - 1]; all_product %= MOD;
	ans[x] = all_product;

}

void solve()
{
	init();
	cin >> n;
	for (Int i = 0; i < n - 1; i++) {
		cin >> a >> b; a--, b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	dfs1(1);
	dfs2(1);
	dfs3(1);

	for (Int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);
	solve();
	return 0;
}


Measured memory_bytes: 49804
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

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

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 2e5;
ll n, k;
V<ll> A;
bool check(ll a){
  ll s = 0;
  for(ll b:A){
    if(b*b<=a) s--;
    if(b==0){
      s += (a>=0 ? n : 0);
    }else if(b>0){
      ll c = a/b;
      if(c*b>a) c--;
      s += upper_bound(all(A), c)-A.begin();
    }else{
      ll c = a/b;
      if(c*b>a) c++;
      s += n-(lower_bound(all(A), c)-A.begin());
    }
  }
  return s/2>=k;
}
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  FOR(i, 0, n){
    int a;
    cin >> a;
    A.pb(a);
  }
  sort(all(A));
  ll ng = -LINF, ok=LINF, mid;
  while(ok-ng>1){
    mid = (ok+ng)/2;
    (check(mid) ? ok : ng) = mid;
  }
  cout << ok << endl;
}

Measured memory_bytes: 5312
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q < p:
            return ide_ele
        p += num - 1
        q += num - 1
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # seg tree初期値 (単位元)
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    def isOK(mid, m, value):
        a = query(m, mid - 1)
        return a >= value


    B = A[::]

    for _ in range(Q):
        T, X, V = [int(x) for x in input().split()]
        if T == 1:
            update(X - 1, V)
            B[X - 1] = V
        elif T == 2:
            print(query(X - 1, V - 1))
        else:
            a = query(X - 1, N - 1)
            if a < V:
                print(N + 1)
            else:
                if B[X - 1] >= V:
                    print(X)
                    continue
                ok = N - 1
                ng = X - 1

                while abs(ok - ng) > 1:
                    mid = (ok + ng) // 2
                    if isOK(mid, X - 1, V):
                        ok = mid
                    else:
                        ng = mid

                print(ok)


if __name__ == '__main__':
    main()


Measured memory_bytes: 107488
#include <cstdio>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, n)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (1 << 20)
int g[20][20];
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    rep(i, n) rep(j, n) g[i][j] = INF;
    rep(i, m) {
        int p, q, r, s;
        scanf("%d,%d,%d,%d", &p, &q, &r, &s);
        p--, q--;
        g[p][q] = r; g[q][p] = s;
    }
    rep(i, n) g[i][i] = 0;
    rep(k, n) rep(i, n) rep(j, n) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }

    int w, x, y, z;
    scanf("%d,%d,%d,%d", &w, &x, &y, &z);
    w--, x--;
    printf("%d\n", y - (z + g[w][x] + g[x][w]));

    return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
ll a,b;
int main()
{
	scanf("%lld%lld",&a,&b);
	int ans=0;
	while(a<=b)a*=2,ans++;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;


int n, m, d, ans;
char c[102][102];

int main() {

	cin >> n >> m >> d;
	rep(i, n)rep(j, m)cin >> c[i][j];

	rep(i, n) {
		rep(j, m) {
			int cnt = j;
			int tmp = 0;
			while (cnt < m) {
				if (c[i][cnt] == '.') {
					cnt++;
					tmp++;
					if (tmp == d) {
						ans++;
						break;
					}
				}
				else {
					break;
				}
			}
		}
	}
	rep(i, m) {
		rep(j, n) {
			int cnt = j;
			int tmp = 0;
			while (cnt < n) {
				if (c[cnt][i] == '.') {
					cnt++;
					tmp++;
					if (tmp == d) {
						ans++;
						break;
					}
				}
				else {
					break;
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

int main(int argc, char const* argv[])
{
	VVL c(3,VL(3));
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> c[i][j];
		}
	}
	VL a(3,0),b(3,0);
	for (int i = 0; i < 3; i++) {
		a[i] = c[0][i] - b[0];
	}
	for (int i = 0; i < 3; i++) {
		b[i] = c[i][0] - a[0];
	}

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (c[i][j] != a[j] + b[i]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int N;
    int input,ans = 0;
    vector<int> a;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> input;
        a.push_back(input);
    }
    sort(a.begin(),a.end(),greater<int>());
    for(int i=0;i<N;i++){
        if(i%2 == 0) ans += a[i];
        else ans -= a[i];
    }
    cout << ans << endl;
    return 0;
}


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

int NumFlips(int start, int goal);

int main()
{
    int N, K;

    cin >> N >> K;
    double n = static_cast<double>(N), k = static_cast<double>(K);

    double p = 0;
    int flips = 0;

    for (int i = 1; i <= N; i++)
    {
        if (i >= K)
        {
            p += 1.0/n;
        }
        else
        {
            flips = NumFlips(i, K);
            if (flips <= 33)
                p += (1.0/(pow(2.0, flips))) * (1.0/n);
        }

    }
    
    cout << fixed << setprecision(12) << p << endl;

}

int NumFlips(int start, int goal)
{
    int count = 0;
    while (start < goal)
    {
        count++;
        start *= 2;
    }

    return count;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1000000007;
const int INF = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};

const ll MAX = 200000;
ll inv[MAX], fac[MAX], finv[MAX];

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
 
void settable() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i <=MAX ; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll choose(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
ll modpow(ll n, ll k){
    ll rtn = 1;
    while(k > 0){
        if(k&1) rtn = rtn * n % MOD;
        n = n * n % MOD;
        k = k >> 1;
    }
    return rtn;
}

int main(){
	settable();
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
	sort(a.begin(), a.end());
	mint ans = 0;
	for(int i = 1; i <= n-k+1; i++){
		ans += a[n-i]*choose(n-i,k-1);
	}
	for(int i = 0; i <= n-k; i++){
		ans -= a[i]*choose(n-1-i,k-1);
	}
	cout << ans.x << endl;
}

Measured memory_bytes: 5376
N = int(input())
A = list(map(int, input().split()))

"""
cum = [[0]*(N) for i in range(N)]
for i in range(N):
  c = 0
  for j in range(i, N):
    c += A[j]
    cum[i][j] = c
"""
cum = [0]
for a in A:
  cum.append(cum[-1] + a)


dp = [[0]*N for i in range(N)]

for n in range(1, N+1):
  for i in range(N-n):
    j = i + n
    min_cost = 0
    for k in range(i, j):
      if min_cost == 0:
        min_cost = dp[i][k] + dp[k+1][j]
      else:
        min_cost = min(min_cost, dp[i][k]+dp[k+1][j])
    
    dp[i][j] = min_cost + (cum[j+1]-cum[i])

print(dp[0][N-1])

Measured memory_bytes: 43756
n = int(input())
ws = list(map(int,input().split()))
ans = abs(sum(ws[1:]) - ws[0])
a = 1
for i in range(1, n):
    if abs(sum(ws[i:]) - sum(ws[:i])) <= ans:
        ans = abs(sum(ws[i:]) - sum(ws[:i]))
    else:
        if a:
        	print(ans)
        a = 0
if a:
	print(ans)

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

int string_len(char str[]){
  int len = 0;
  while(str[len])
    len++;
  return len;
}

int main(void){
  char S[50];
  char T[50];
  bool ans = true;
  cin >> S >> T;
  int len = string_len(S);
  for(int i = 0; i < len; i++){
    if(S[i] != T[i]){
      ans = false;
      break;
    }
  }
  if(ans) cout << "Yes" << "\n";
  else cout << "No" << "\n";
  return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>

int main(){
int a=0,b=0;
scanf("%d %d",&a,&b);
if(a<b){
	printf("a < b\n");
}
else
if(a>b){
	printf("a > b\n");
}
else
if(a==b){
	printf("a == b\n");
	
}
return 0;
}


Measured memory_bytes: 1988
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long x,k,d;
	cin>>x>>k>>d;
	x=abs(x);
	if(x/k>=d)
	{
		cout<<x-k*d;
	}
	else 
	{
		long long y=x%d;
		long long i=(x-y)/d;
		if((k-i)%2) y=abs(y-d);
		cout<<y<<endl;
	}
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> h(N);
    rep(i, N) cin >> h[i];

    int res = 0;
    while (true) {
        if (*max_element(h.begin(), h.end()) == 0) break;

        int i = 0;
        while(i < N) {
            if (h[i]==0) i++;
            else {
                res++;
                while(i < N && h[i] > 0) {
                    h[i]--;
                    i++;
                }
            }
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256