akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int H, W, i, j;
    while(1){
    cin >> H >> W ;
    if(H==0 && W==0) break;
    for(i=0; i < H; i++){
        for(j=0; j<W; j++){
            if( i == 0 || i == H-1 || j == 0 || j == W-1 ) cout << '#';
            else cout << '.';
        }
        cout << endl;
    }
    cout << endl;
    }

    return 0;
}


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

int main (){
    string s;
    cin >> s;
    int l=s.length();
    string ans;
    rep(i,l){
        if(s[i]=='0') ans+='0';
        else if(s[i]=='1') ans+='1';
        else if(s[i]=='B') {
            if(int x=ans.length()==0) continue;
            ans.erase(ans.end()-1);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
function CombinationWithReplacement(list, size)
    size <= 0 && return []
    result = Array{Int64}[]
    CombinationWithReplacement!(list, size, 1, [], result)
    return result
end

function CombinationWithReplacement!(list, size, start, progress, result)
    size == 0 && push!(result, progress) |> return 

    for i in start:length(list)
        CombinationWithReplacement!(list, size - 1, i, push!(copy(progress), list[i]), result)
    end
end

function main()
    N, M, Q = map(x -> parse(Int, x), split(readline()))
    abcds = [map(x -> parse(Int, x), split(readline())) for i ∈ 1:Q]

    mx = 0
    for As ∈ CombinationWithReplacement(1:M, N)
        score = 0
        for i ∈ 1:Q
            (a, b, c, d) = abcds[i]
            score += d * (As[b] - As[a] == c)
        end
        mx = max(mx, score)  
    end
    println(mx)
end

main()


Measured memory_bytes: 266964
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mod 1000000007
signed main()
{
   int n;
   cin>>n;
   int pre=0,ans=0;
   for(int i=0;i<n;i++)
   {
    int x;
    cin>>x;
    ans=(ans+pre*x)%mod;
    pre=(pre+x)%mod;
   }
   cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
int SG(int x,int k){
	if (x<k) return 0;
	if (x%k==0) return x/k;
	int y=x/k+1;
	return SG(x-max(1,x%k/y)*y,k);
}
int n;
int main(){
	scanf("%d",&n);
	int ans=0;
	for (int i=1;i<=n;++i){
		int x,k;
		scanf("%d%d",&x,&k);
		ans^=SG(x,k);
	}
	puts(ans==0?"Aoki":"Takahashi");
}

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

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

    map<pair<int,int>, int> mp;
    int h,w,m; cin >> h >> w >> m;
    vector<pair<int,int>> row(h), col(w);

    rep(i,h) row[i] = make_pair(0, i);
    rep(j,w) col[j] = make_pair(0, j);

    int ht, wt;
    rep(i,m){
        cin >> ht >> wt;
        --ht; --wt;
        mp[make_pair(ht,wt)] = 1;
        row[ht].first++;
        col[wt].first++;
    }

    sort(row.begin(), row.end(), greater<pair<int,int>>());
    sort(col.begin(), col.end(), greater<pair<int,int>>());

    int rt = row[0].first, ct = col[0].first, cnt = 0;
    int ans = rt + ct - mp[make_pair(row[0].second, col[0].second)];
    for(int i = 0; row[i].first == rt && cnt <= m+1; ++i){
        for(int j = 0; col[j].first == ct && cnt <= m+1; ++j){
            ht = row[i].second, wt = col[j].second;
            int tmp = row[i].first + col[j].first - mp[make_pair(ht, wt)];
            if(ans < tmp){
                ans = tmp;
                break;
            }
            cnt++;
        }
    }
    
    cout << ans << endl;

}

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

vector<string> ans;
vector<bool> appear(30);

void enc(string& str, int n, string& itms){
	if(n<(int)str.length()){
		if(itms[n]=='z'){
			enc(str, n+1, itms);
		}else{
			if(appear[itms[n]-'a']){
				enc(str,n+1, itms);
				
			}
			if(!appear[itms[n]-'a'+1]){
				itms[n]++;
				appear[itms[n]-'a'] = true;
				enc(str, n+1, itms);
				appear[itms[n]-'a'] = false;
				itms[n]--;
				
			}
		}
		
	}else{
		string tmp = itms;
		for(char c='b'; c<='z'; c++){
			for(int j=0; j<(int)tmp.length(); j++){
				if(tmp[j]==c){
					tmp[j]--;
					break;
				}
			}
		}
		if(tmp == str){
			ans.push_back(itms);
		}
	}
}

int main(){
	appear[0] = true;
	while(1){
		string str;
		cin >> str;
		if(str=="#") break;
		
		ans.clear();
		fill(appear.begin()+1, appear.end(), false);
		string tmp = str;
		enc(str, 0, tmp);
		sort(ans.begin(), ans.end());
		
		cout << ans.size() << endl;
		if((int)ans.size() <= 10){
			for(int i=0; i<(int)ans.size(); i++){
				cout << ans[i] << endl;
			}
		}else{
			for(int i=0; i<5; i++){
				cout << ans[i] << endl;
			}
			for(int i=ans.size()-5; i<(int)ans.size(); i++){
				cout << ans[i] << endl;
			}
		}
	}
	return 0;
}

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

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b && c!=a)
    {
        cout<<"Yes"<<endl;
    }
    else if(a==c && b!=a)
    {
        cout<<"Yes"<<endl;
    }
    else if(c==b && c!=a)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramA
    {
        static void Main()
        {
            System.Console.WriteLine(Math.Min(NextInt * NextInt, NextInt));
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 13268
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main() {
    int N;
    cin >> N;
    vector<int> Ais;
    for (int i = 0; i < N; i++) {
        int Ai;
        cin >> Ai;
        Ais.push_back(Ai);
    }
    ll cnt = 0;
    for (int i = (int)Ais.size() - 1; i >= 0; i--) {
        if (Ais[i] > i) {
            cout << -1 << endl;
            return 0;
        } else {
            cnt += Ais[i];
            while (i > 0) {
                if (Ais[i-1] == Ais[i] - 1) {
                    i--;
                    continue;
                } else if (Ais[i-1] < Ais[i] - 1) {
                    cout << -1 << endl;
                    return 0;
                } else {
                    break;
                }
            }
        }
    }
    cout << cnt << endl;
}



Measured memory_bytes: 2032
#include<stdio.h>
int main(void){
    int a[100]={0},i;
    for(i=0;i<=4;i++){
        scanf("%d",&a[i]);
    }
    a[5]=a[0]+a[3];
    a[6]=a[0]+a[4];
    a[7]=a[1]+a[3];
    a[8]=a[1]+a[4];
    a[9]=a[2]+a[3];
    a[10]=a[2]+a[4];

    for(i=6;i<=10;i++){
        if(a[5]>a[i]){
            a[5]=a[i];
        }

    }

    printf("%d\n",a[5]-50);

    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int n;
int res;
bool check(ll a){
  bool three, five, seven;
  three = false;
  five = false;
  seven = false;
  
  string b = to_string(a);
  
  rep(i,b.size()){
    char s = b[i];
    if (s == '3') three = true;
    if (s == '5') five = true;
    if (s == '7') seven = true;
  }
  
  if (three && five && seven) return true;
  else return false;
}

void rec(ll a){
  
  if (a > n) return;
  
  if(check(a)) res++; //753数かどうかcheck

  rec(10 * a + 3); //1の桁に3を追加する場合
  rec(10 * a + 5); //1の桁に5を追加する場合
  rec(10 * a + 7); //1の桁に7を追加する場合
}

int main(){
  cin >> n;
  res = 0;
  rec(0LL);
  
  cout << res;
  return 0;
}

Measured memory_bytes: 256
/*
1,2,...,N の足場がそれぞれh1,h2,...,hNの高さを持つ。
カエルは足場iからi+1かi+2の足場jに対して、|hj-hi|のコストでジャンプ移動する。
足場1から足場Nまでの最小コストを求めよ。

例
4
10 30 40 20
-> 30

制約
2<N<10^5
1<h<10^4

*/

#include <stdio.h>
#define D_SIZE_BUFF 100000
#define TRUE 0
#define FALSE 1

//#define DEBUG
#ifdef DEBUG
# define dprintf(fmt, ...)  printf(fmt, ##__VA_ARGS__);                   
#else
# define dprintf(fmt, ...)
#endif


/*
    cmp
    aとbを比較して、aが小さければTRUEを返す。bが小さければFALSEを返す。
*/
int cmp(int a, int b)
{
    if( a < b ) return TRUE;
    return FALSE;
}

int jumpcost(int ha, int hb)
{
    if( ha < hb ) return (hb - ha);
    else return (ha - hb);
}

int main()
{

    int i,N,tmp,height[D_SIZE_BUFF];
    int ashiba_cost[D_SIZE_BUFF+1];

    // input
    scanf("%d",&N);
    for(i=0;i<N;i++)
    {
        scanf("%d",&height[i]);
        dprintf("h[%d]=%d\n",i,height[i]);

        // ついでにコストの初期化をする
        ashiba_cost[i] = __INT_MAX__;
    }

    // 足場1のコスト0を起点として、足場i+1,i+2の最小コストを順に計算する。
    // すでに保存されているコスト(初期値：無限)と、足場i->i+1への合計コストを比べて小さい方でコストを更新する。
    // 経路は記憶しない。最小コストのみashiba_cost[]に保存する。
    // 合計コストの最大はhmax*Nmax = 10^4*10^5 = 10^9 < INT_MAX

    ashiba_cost[0] = 0;

    // 最後+1個目の足場までコストは計算してしまうことにする。
    for(i=0;i<N-1;i++)
    {
        tmp = ashiba_cost[i]+jumpcost(height[i],height[i+1]);
        dprintf("tmp=%d ",tmp)
        
        // ashiba i+1
        if( TRUE == cmp(ashiba_cost[i+1],tmp) ){ /*そのまま*/ }
        else{ ashiba_cost[i+1] = tmp;}

        tmp = ashiba_cost[i]+jumpcost(height[i],height[i+2]);
        dprintf("tmp=%d\n",tmp)

        // ashiba i+2
        if( TRUE == cmp(ashiba_cost[i+2],tmp) ){ /*そのまま*/ }
        else{ ashiba_cost[i+2] = tmp; }

        dprintf("c[%d]=%d, c[%d]=%d\n",
            i+1,ashiba_cost[i+1],i+2,ashiba_cost[i+2]);
    }

    // 足場Nに保存されたコスト値が最小の合計コスト
    printf("%d",ashiba_cost[N-1]);

    return 0;
}

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

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

    while (1) {
        int n, x;
        cin >> n >> x;
        if (n == 0 && x == 0) {
            break;
        } else {
            int count = 0;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j < i; j++) {
                    for (int k = 1; k < j; k++) {
                        if (i + j + k == x) {
                            count++;
                        }
                    }
                }
            }
            printf("%d\n", count);
        }
    }

    return 0;
}



Measured memory_bytes: 3232
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String input = br.readLine();

			if(input == null){
				break;
			}

			String[] tmpArray = input.split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int q = Integer.parseInt(tmpArray[1]);

			if(n == 0 && q == 0){
				break;
			}

			Node[] nodes = new Node[n + 1];
//			nodes[0] = new Node(0, -1);
//			nodes[0].marked = true;

			nodes[1] = new Node(1, 0);
			nodes[1].marked = true;

			for(int i = 2; i <= n; i++){
				int num = Integer.parseInt(br.readLine());

				nodes[i] = new Node(i, num);
			}

			long sum = 0;

			for(int i = 0; i < q; i++){
				tmpArray = br.readLine().split(" ");
				int tmp = Integer.parseInt(tmpArray[1]);
				if(tmpArray[0].equals("M")){
					nodes[tmp].marked = true;
				}

				else {
					sum += nearest(nodes, tmp);
				}
			}

			System.out.println(sum);
		}
	}

	static int nearest(Node[] nodes, int id){
		while(true){

//			System.out.println("id = "+id);

			if(nodes[id].marked){
				return id;
			}

			id = nodes[id].parent;
		}
	}

}

class Node {
	int id;
	int parent;
	boolean marked = false;

	public Node(int id, int parent){
		this.id = id;
		this.parent = parent;
	}
}


Measured memory_bytes: 100548
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

const ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
int main() {
	int n, a, b, c, d,i,cha=1e+9;
	char s[222222];
	cin >> n >> a >> b >> c >> d >> s;
	a--;
	b--;
	c--;
	d--;
	if (c < d) {
		for (i = a + 1; i < c; i++) {
			if (s[i] == '#'&&s[i - 1] == '#') {
				cout << "No" << endl;
				return 0;
			}
		}
		for (i = b + 1; i < d; i++) {
			if (s[i] == '#'&&s[i - 1] == '#') {
				cout << "No" << endl;
				return 0;
			}
		}
		cout << "Yes" << endl;
	}
	else {
		for (i = a + 1; i < c; i++) {
			if (s[i] == '#'&&s[i - 1] == '#') {
				cout << "No" << endl;
				return 0;
			}
			if (i > b&&s[i] == '.'&&s[i - 1] == '.'&&s[i - 2] == '.'&&cha > 1e+7)
				cha = i;
		}
		if (cha > d + 1)
			cout << "No" << endl;
		else
			cout << "Yes" << endl;
	}
}

Measured memory_bytes: 5120
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]-1].append(x[i][1]-1)
    adj[x[i][1]-1].append(x[i][0]-1)

global ans
ans = [0]*N

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(0, 0)
'''
for i in range(N):
    print(ans[i], '', end='')
'''
print(*ans)

Measured memory_bytes: 276380
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int W,a,b;
	scan(W>>a>>b);
	if(b>a+W) prin(b-a-W);
	else if(a>b+W) prin(a-b-W);
	else prin(0);
	return 0;
}


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

int main() {
  int n,m;
  cin>>n>>m;
  vector<int> d;
  for (int i=1; i*i<=m; i++) {
    if (m%i==0) {
      d.push_back(i); d.push_back(m/i);
    }
  }
  sort(d.begin(),d.end());
  reverse(d.begin(),d.end());
  rep(i,d.size()) {
    if (m/d[i]>=n) {
      cout<<d[i]<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // ABC158D - String Formation

        Scanner sc = new Scanner(System.in);

        String s = sc.next();

        int q = sc.nextInt();

        int[] t = new int[q];
        int[] f = new int[q];
        String [] c = new String[q];

        StringBuilder prefix = new StringBuilder();
        StringBuilder suffix = new StringBuilder();

        boolean isReverse = false;

        for (int i = 0; i < q; i++) {
            t[i] = sc.nextInt();
            if (t[i] == 2) {
                f[i] = sc.nextInt();
                c[i] = sc.next();
                if (!isReverse) {
                    if (f[i] == 1) {
                        prefix.insert(0, c[i]);
                    } else {
                        suffix.append(c[i]);
                    }
                } else {
                    if (f[i] == 2) {
                        prefix.insert(0, c[i]);
                    } else {
                        suffix.append(c[i]);
                    }
                }
            } else {
                isReverse = !isReverse;
            }
        }

        StringBuilder ans = new StringBuilder(prefix + s + suffix);

        if (isReverse) {
            ans = ans.reverse();
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 156732
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N, LIST):  # ワーシャルフロイド法:全頂点対最短経路 O(n**3)
    DIST = deepcopy(LIST)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


n, m, r = map(int, input().split())
town = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n, mat)
for route in permutations(town, r):
    bfo, tmp = route[0], 0
    for i in route[1:]:
        tmp += dist[bfo - 1][i - 1]
        bfo = i
    ans = min(ans, tmp)
print(ans)


Measured memory_bytes: 78436
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ll n;
    cin>>n;
    ll arr[n+1];
    for(ll i = 0;i<n;i++){
        cin>>arr[i];
    }
    double ans = 1;
    for(ll i = 0;i<n;i++){
        ans *= arr[i];
    }
   // cout<<ans<<"\n";
   double sum = 0;
    for(ll i = 0;i<n;i++){
    double e = ans;
    sum += (e/arr[i]);
    //cout<<sum<<"\n";
    }
    cout<<fixed;
    cout<<setprecision(25)<<ans/sum;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;

int main(){
    int N;cin>>N;
    vector<int> A(N),B(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    for(int i=0;i<N;i++){
        cin>>B[i];
    }
    sort(all(A));
    sort(all(B));

    A.push_back(INF);
    B.push_back(INF);

    vector<int> S(2*N,0);
    int anow=0,bnow=0;
    
    while(anow+bnow<2*N){
        if(A[anow]<B[bnow]){
            S[anow+bnow]=1;
            anow++;
        }else{
            S[anow+bnow]=0;
            bnow++;
        }
    }
    ll ans=1;

    int acnt=0,bcnt=0;
    for(int i=0;i<2*N;i++){
        if(S[i]==1){
            if(bcnt>0){
                ans=ans*bcnt%mod;
                bcnt--;
            }else{
                acnt++;
            }
        }
        else{
            if(acnt>0){
                ans=ans*acnt%mod;
                acnt--;
            }
            else{
                bcnt++;
            }
        }
    }

    cout<<ans<<endl;
}

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


int main(){
  int n,q;
  while(cin>>n>>q,n){
    vector<int> par(n);
    par[0]=0;
    for(int i=1;i<n;i++){
      int p;
      cin>>p;
      p--;
      par[i]=p;
    }
    vector<int> rootpar(n,0);
    int r=max(sqrt(n),5.0)+10;
    for(int i=0;i<n;i++){
      int v=par[i];
      for(int j=0;j<r;j++){
	v=par[v];
      }
      rootpar[i]=v;
    }
    vector<int> marked(n,0);
    marked[0]=1;
    vector<int> lowmark(n,0);
    lowmark[0]=1;
    long long int res=0;
    for(int i=0;i<q;i++){
      char cmd;
      int v;
      cin>>cmd>>v;
      v--;
      if(cmd=='M'){
	marked[v]=1;
	int nex=v;
	for(int i=0;i<2*r;i++){
	  lowmark[nex]=1;
	  nex=par[nex];
	}
	continue;
      }
      if(cmd=='Q'){
	int nex=v;
	bool ressed=false;
	for(int i=0;i<2*r+3 && !ressed;i++){
	  if(marked[nex]){
	    res+=nex+1;
	    ressed=true;
	  }
	  else{
	    nex=par[nex];
	  }
	}
	if(ressed)continue;
	while(!lowmark[rootpar[nex]]) nex=rootpar[nex];
	for(int i=0;i<2*r;i++){
	  if(marked[nex]){
	    res+=nex+1;
	    break;
	  }
	  nex=par[nex];
	}
      }
      
    }
    cout<<res<<endl;
  }
  return 0;

}

Measured memory_bytes: 4308
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 7;

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

/*-------------------------------------------*/

const double pi = acos(-1.0);

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

    int n;
    cin >> n;
    ll X[100], Y[100];
    rep(i, n) cin >> X[i] >> Y[i];
    ll ans = 0;
    rep(i, 360) {
        ll x = 0, y = 0;
        rep(j, n) {
            if(cos(i * pi / 180) * X[j] + sin(i * pi / 180) * Y[j] > 0.0) {
                x += X[j];
                y += Y[j];
            }
        }
        chmax(ans, x * x + y * y);
    }
    printf("%.12f\n", sqrt(ans));
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  int k;
  cin >> k;
  string s;
  cin >> s;
  if (s.size() <= k)
    cout << s << endl;
  else
    cout << s.substr(0, k) << "..." << endl;

  return 0;
}


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

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

class Graph{
    public:
    typedef struct Edge{
        ll from, to, cost;
        Edge(ll f, ll t, ll c): from(f),to(t),cost(c){}
    } Edge;

    bool isDirected;
    ll INF = 1LL << 62;
    ll v; // 頂点数
    std::vector<Edge> edges;  // 辺のリスト
    std::vector<std::vector<std::pair<ll,ll>>> list;  // 隣接リスト
    //std::vector<std::vector<ll>> matrix; // 隣接行列
    
    Graph() : isDirected(false){ init(0); }
    Graph(ll n, bool isDirected=false) : isDirected(isDirected) { init(n); }
    void init(ll n){
        v=n;
        edges.clear();
        list.assign(n, std::vector<std::pair<ll,ll>>());
        //matrix.assign(n, std::vector<ll>(n, INF));
    }
    void connect(ll from, ll to){
        con(from, to, 1);
        if(!isDirected) con(to, from, 1);
    }
    void connect(ll from, ll to, ll cost){
        con(from, to, cost);
        if(!isDirected) con(to, from, cost);
    }
    void con(ll from, ll to, ll cost){
        edges.push_back(Edge(from,to,cost));
        list[from].push_back(std::make_pair(to, cost));
        //matrix[from][to] = cost;
    }
};

int main(){
    ll n;
    cin>>n;
    Graph g(n);
    ll a,b;
    REP(i,n-1){
        cin>>a>>b;
        g.connect(a-1,b-1);
    }
    int label[200005]={};
    label[0]=1;
    queue<ll> que;
    que.push(0);
    while(!que.empty()){
        ll v = que.front(); que.pop();
        for(auto i : g.list[v]){
            if(label[i.first]==0){
                label[i.first]=3-label[v];
                que.push(i.first);
            }
        }
    }
    int l1=0;int l2=0;
    REP(i,n){
        if(label[i]==1)l1++;
        else if(label[i]==2)l2++;
    }
    int num1=n/3+(n%3>=1);
    int num2=n/3+(n%3==2);
    if(l1<l2){
        REP(i,n)label[i]=3-label[i];
        swap(l1,l2);
    }
    int val[200005]={};
    if(n-num1-num2>=l2){
        int x=3;
        REP(i,n)if(label[i]==2){
            val[i]=x; x+=3;
        }
        if(x<=n)REP(i,n)if(val[i]==0){
            val[i]=x; x+=3;
            if(x>n)break;
        }
        x=1;
        REP(i,n)if(val[i]==0){
            val[i]=x; x+=3;
            if(x>n)break;
        }
        x=2;
        REP(i,n)if(val[i]==0){
            val[i]=x; x+=3;
            if(x>n)break;
        }
        REP(i,n)if(val[i]!=0){
            cout<<val[i]<<" ";
        }
        cout<<endl;
        return 0;
    }
    else if(l1<=n-num2){
        int x=1;
        REP(i,200005)if(label[i]==1){
            val[i]=x; x+=3;
        }
        x=2;
        REP(i,200005)if(label[i]==2){
            val[i]=x; x+=3;
        }
        x=3;
        REP(i,200005)if(val[i]>n){
            if(x>n){
                cout<<"-1"<<endl; return 0;
            }
            val[i]=x; x+=3;
        }
        REP(i,n)if(val[i]!=0){
            cout<<val[i]<<" ";
        }
        cout<<endl;
        return 0;
    }
    else{
        cout<<"-1"<<endl; return 0;
    }
}

Measured memory_bytes: 29608
gets.to_i.times do
  y,m,d = gets.split.map(&:to_i)
  res = 0
  while y < 1000
    d += 1
    res += 1
    md = 19
    if y % 3 == 0 || m % 2 == 1
       md = 20
    end
    if d > md
        d = 1
        m += 1
    end
    if m > 10
      m = 1
      y += 1
    end
  end
  puts res
end

Measured memory_bytes: 6108
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int tmp = n;
        int sn = 0;
        while(tmp > 0){
            sn += tmp % 10;
            tmp /= 10;
        }
        pw.println(n%sn == 0 ? "Yes" : "No");
        pw.flush();
    }

    static class GeekInteger {
        public static void save_sort(int[] array) {
            shuffle(array);
            Arrays.sort(array);
        }
 
        public static int[] shuffle(int[] array) {
            int n = array.length;
            Random random = new Random();
            for (int i = 0, j; i < n; i++) {
                j = i + random.nextInt(n - i);
                int randomElement = array[j];
                array[j] = array[i];
                array[i] = randomElement;
            }
            return array;
        }
 
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

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

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

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 33004
import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())
S = readline().rstrip()

cnt = [0] * (N + 1)
for i in range(1,len(S)):
  if S[i - 1:i + 1] == "AC":
    cnt[i + 1] = 1
    
for i in range(1,len(cnt)):
  cnt[i] = cnt[i - 1] + cnt[i]
  
for i in range(Q):
  l,r = map(int,readline().split())
  print(cnt[r] - cnt[l])


Measured memory_bytes: 7964
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;
typedef long long ll;

int main(){
//	freopen("in.txt", "r", stdin);
//	freopen("g.txt", "w", stdout);
	ll a, b;
	scanf("%lld%lld", &a, &b);
	
	//cerr<<(1LL << 60)<<endl;
	if(a == b){
		puts("1");
		return 0;
	}
	if(a > b){
		puts("0");
		return 0;
	}
	
	int bit;
	ll mid = 0, ans = 0, l, r, s, t;
	for(int i = 60;i >= 0;--i){
		if(((a >> i) & 1) ^ ((b >> i) & 1)){  
			mid = (1LL << i);
			bit = i;
			break;
		}
		if((a >> i) & 1)a ^= (1LL << i), b ^= (1LL << i);
	}
	
	ans = mid - a;
	l = r = mid;
	for(int i = bit - 1;i >= 0;--i){
		if((b >> i) & 1){
			r |= ((1LL << (i + 1)) - 1);
			break;
		}
	}
	ans += r - l + 1;
	
	s = mid + a, t = mid * 2 - 1;
	ans += t - s + 1;
	
	if(s <= r)ans -= (r - s + 1);
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
inner_sum, total = 0, 0
for i in range(N):
    inner_sum += A[i]

for i in range(N-1):
    inner_sum -= A[i]
    total += A[i] * inner_sum
    
print(total % (10 ** 9 + 7))

Measured memory_bytes: 104896
def digit_sum(n)
  sum = 0
  while n!=0 do
    sum += n%10
    n /= 10
  end
  sum
end

n,a,b = gets.chomp.split.map(&:to_i)

ans = (1..n).map {|i| [i,digit_sum(i)]}
            .select {|d| a <= d[1] && d[1] <= b}
            .inject(0) {|sum, d| sum + d[0]}
            
puts ans

Measured memory_bytes: 2172
{-# LANGUAGE PartialTypeSignatures #-}
module Main (main) where

import Control.Monad
import qualified Data.ByteString.Char8 as C8
import qualified Data.Char as C
import qualified Data.List as L
import qualified Data.Set as Set

main :: IO ()
main = do
  [n,k] <- readInts
  replicateM k (readInts >> readInts) >>= output . solve n . concat

solve :: Int -> [Int] -> _
solve n = Set.size . (xs Set.\\) . Set.fromList
  where
    xs = Set.fromList [1..n]

output :: _ -> IO ()
output = print

-- utils
readInts :: IO [Int]
readInts = L.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine


Measured memory_bytes: 4820
<?php
  $input = trim(fgets(STDIN));
  list($n, $m) = explode(' ', $input);
	$max = $n;
	$min = $n;

  $input = trim(fgets(STDIN));
  $num = explode(' ', $input);
	foreach($num as $value){
      $nums[] = abs($value);
    }
  $result = null;
	while(true){
    	if(in_array($max, $nums) === true){
        	$max = $max + 1;
        }else{
        	$result[] = $max;
        }
      	if(in_array($min, $nums) === true){
        	$min = $min - 1;
        }else{
        	$result[] = $min;
        }
      if(isset($result)){
      	break;
      }
    }
echo min($result);
?>

Measured memory_bytes: 16164
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static final int BIG_NUM  = 2000000000;
    public static final int MOD  = 1000000007;
 
    public static void main(String[] args) {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String buffer[] = new String[2];
        int N,X,ans;
 
        while(true){
 
            try {
                buffer = br.readLine().split("\\s+");
                N = Integer.parseInt(buffer[0]);
                X = Integer.parseInt(buffer[1]);
 
                if(N == 0 && X == 0)break;
 
                ans = 0;
 
                for(int a = 1; a <= N-2; a++){
                    for(int b = a+1; b <= N-1; b++){
                        for(int c = b+1; c <= N; c++){
                            if(a+b+c == X){
                                ans++;
                            }
                        }
                    }
                }
 
                System.out.printf("%d\n", ans);
 
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}


Measured memory_bytes: 26232
import java.util.*;
public class Main {
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        long[] map = new long[3*N];
        for (int i = 0; i < N*3; i++) {
        	map[i] = sc.nextLong();
        }
        
        Arrays.sort(map);
        
        long ans = 0;
        for (int i = 0; i < N; i++) {
        	ans += map[3*N-2-(2*i)];
        }
        System.out.println(ans);
    }
}



Measured memory_bytes: 99408
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<math.h>
#include<stack>
#include<vector>
#define maxn 50000000
typedef long long ll;
using namespace std;
int A,B,M,a[maxn],b[maxn],x[maxn],y[maxn],c[maxn];
int cost[maxn],rec=0,tmp=0;
int arr[maxn],brr[maxn],crr[maxn];


int main()
{
	cin>>A>>B>>M;
	for(int i=1;i<=A;i++)
	{
		cin>>a[i];
		arr[a[i]]++;
	}
	for(int i=1;i<=B;i++)
	{
		cin>>b[i];
		brr[b[i]]++;
	}
	for(int i=0;i<=maxn;i++)
	{
		if(arr[i]!=0)
		{
			rec+=i;
			break;
		}
	}
	for(int i=0;i<=maxn;i++)
	{
		if(brr[i]!=0)
		{
			rec+=i;
			break;
		}
	}
	for(int i=1;i<=M;i++)
	{
		cin>>x[i]>>y[i]>>c[i];
		cost[i] = a[x[i]]+b[y[i]]-c[i];
		if(cost[i]<0)
		{
			cost[i] = 0;
		}
		crr[cost[i]]++;
	}
	for(int i=0;i<=maxn;i++)
	{
		if(crr[i]!=0)
		{
			tmp=i;
			break;
		}
	}
	int t;
	t=tmp<rec?tmp:rec;
	cout<<t<<endl;
	return 0;
}

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

int main() {
	int n;
	std::cin >> n;
	std::vector<std::pair<int, int>>r(n), b(n);
	std::vector<bool>used(n, 0);
	for (int i = 0; i < 2 * n; i++) {
		if (i < n)std::cin >> r[i].first >> r[i].second;
		else std::cin >> b[i - n].first >> b[i - n].second;
	}

	std::sort(r.begin(), r.end(), [](const auto a, const auto b) {return a.first > b.first; });
	std::sort(b.begin(), b.end(), [](const auto a, const auto b) {return a.second < b.second; });
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int minIdx = -1;
		for (int j = 0; j < n; j++) {
			if (r[i].second < b[j].second&&r[i].first < b[j].first&&!used[j]) {
				minIdx = j;
				break;
			}
		}
		if (minIdx == -1)continue;
		used[minIdx] = true;
		ans++;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_map>

//#include"GraphAlgorithm.hpp"
//#include"DataStructure.hpp"
//using namespace graph_algorithm;
//using namespace data_structure;

using namespace std;
using cMatrixRepEdges=std::vector<std::vector<int>>;
pair<vector<int>,int> solve_by_EdmondsKarp_helper(const cMatrixRepEdges& ResidualNetwork,int source,int sink){
	if(ResidualNetwork.empty())return make_pair(vector<int>(),0);

	vector<bool> IsVisit(ResidualNetwork.size(),false);
	vector<int> Parents(ResidualNetwork.size(),-1);
	queue<pair<int,int>> Q;
	Q.push(make_pair(source,INT_MAX));
	IsVisit[source]=true;

	int ans=0;
	while(!Q.empty()){
		auto now=Q.front();
		Q.pop();
		if(now.first==sink){
			ans=now.second;
			break;
		}

		for(int i=0;i<ResidualNetwork.size();++i){
			if(ResidualNetwork[now.first][i]>0 && !IsVisit[i]){
				IsVisit[i]=true;
				Parents[i]=now.first;
				Q.push(make_pair(i,min(now.second,ResidualNetwork[now.first][i])));
			}
		}
	}

	return make_pair(Parents,ans);
}

cMatrixRepEdges solve_by_EdmondsKarp(const cMatrixRepEdges& FlowNetwork,int source,int sink){
	if(FlowNetwork.empty() || source<0 || FlowNetwork.size()<=source || sink<0 || FlowNetwork.size()<=sink)return cMatrixRepEdges();

	cMatrixRepEdges ResidualNetwork=FlowNetwork;
	cMatrixRepEdges AnsFlow(FlowNetwork.size(),vector<int>(FlowNetwork.size(),0));

	while(1){
		auto ans=solve_by_EdmondsKarp_helper(ResidualNetwork,source,sink);
		//source??????sink???????????????????????????????????£???
		if(ans.first[sink]<0)break;

		int to=sink;
		int from=ans.first[sink];
		while(to!=source){
			if(FlowNetwork[from][to]>0){
				AnsFlow[from][to]+=ans.second;
				ResidualNetwork[from][to]=FlowNetwork[from][to]-AnsFlow[from][to];
				ResidualNetwork[to][from]=AnsFlow[from][to];
			}
			else{
				AnsFlow[to][from]-=ans.second;
				ResidualNetwork[to][from]=FlowNetwork[to][from]-AnsFlow[to][from];
				ResidualNetwork[from][to]=AnsFlow[to][from];
			}

			to=from;
			from=ans.first[from];
		}
	}

	return AnsFlow;
}

const double pi=4*atan(1.0);

int mod=1000000007;

int main() {
	int X,Y,M;
	cin>>X>>Y>>M;

	cMatrixRepEdges Edges(X+Y+2,vector<int>(X+Y+2,0));
	for(int i=0;i<M;++i){
		int x,y;
		cin>>x>>y;

		Edges[x][X+y]=1;
	}

	for(int i=0;i<X;++i){
		Edges[X+Y][i]=1;
	}

	for(int i=X;i<X+Y;++i){
		Edges[i][X+Y+1]=1;
	}

	auto ans=solve_by_EdmondsKarp(Edges,X+Y,X+Y+1);

	int sum=0;
	for(int i=0;i<X;++i){
		sum+=ans[X+Y][i];
	}

	cout<<sum<<endl;
	
	//system("pause");
	return 0;
}

Measured memory_bytes: 3512
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>

using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define rrep(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i, x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
#define put2darr(arr, row, col) rep(i, row) { rep(j, col) { printf("%18d", arr[i][j]); } cout << endl; }

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;
}

/* 1..10
 * rep:   0 1 2 3 4 5 6 7 8 9
 * reps:  1 2 3 4 5 6 7 8 9 10
 * rrep:  9 8 7 6 5 4 3 2 1 0
 * rreps: 10 9 8 7 6 5 4 3 2 1
 */

int n, m;
int a;
int b;
vector<pair<ll ,ll>> ab;

int main() {
    cin >> n >> m;
    rep(i, n) {
        cin >> a >> b;
        ab.push_back(make_pair(a, b));
    }
    sort(all(ab));
    ll sum = 0;
    int i = 0;
    ll ans = 0;
    while (sum < m) {
        if (sum + ab[i].second> m) {
            ans += (m - sum) * ab[i].first;
            sum += m - sum;
        } else {
            ans += ab[i].first * ab[i].second;
            sum += ab[i].second;
        }
        i++;
    }
    cout << ans << endl;


}




Measured memory_bytes: 2420
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

constexpr int MOD = 1e9 + 7;
vector<vector<int> > G;
ll dp[100010][2];

ll rec(int v,int pv,int c){
    if(dp[v][c]!=-1) return dp[v][c];
    ll ret = 1;
    for(int nv : G[v]){
        if(nv==pv) continue;
        if(c==0){ // v color is white
            (ret *= rec(nv,v,0) + rec(nv,v,1)) %= MOD;
        } else {
            (ret *= rec(nv,v,0)) %= MOD;
        }
    }
    return dp[v][c] = ret;
}


int main(void){
    int N;cin >> N;
    G.resize(N);
    int x,y;
    for(int i=0;i<N-1;++i){
        cin >> x >> y;
        --x;--y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=0;i<=N;++i) for(int j=0;j<2;++j) dp[i][j] = -1;

    cout << (rec(0,-1,0) + rec(0,-1,1))%MOD << endl;

    return 0;
}

Measured memory_bytes: 15616
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
int MOD=1000000007;
signed main(){
    int n;cin>>n;
    vector<pair<int,int>> a(n);
    //a[0]={-1,-1};
    rep(i,n){
        cin>>a[i].first;
        a[i].second=i+1;
    }
    sort(ALL(a));
    vector<vector<int>> dp(n+5,vector<int>(n+5,0));
    //dp[1][0]=abs(a[n-1].second-1)*a[n-1].first;
    //dp[0][1]=abs(a[n-1].second-n)*a[n-1].first;
    int res=0;
    rep(i,n+1){
        rep(j,n+1){
            if(i+j==0)continue;
            if(i==0){
                dp[i][j]=max(dp[i][j],a[n-(i+j)].first*(abs(a[n-(i+j)].second-(n-j+1)))+dp[i][j-1]);
                continue;
            }
            else if(j==0){
                dp[i][j]=max(dp[i][j],a[n-(i+j)].first*(abs(a[n-(i+j)].second-i))+dp[i-1][j]);
                continue;
            }
            dp[i][j]=max(dp[i][j],a[n-(i+j)].first*(abs(a[n-(i+j)].second-i))+dp[i-1][j]);
            dp[i][j]=max(dp[i][j],a[n-(i+j)].first*(abs(a[n-(i+j)].second-(n-j+1)))+dp[i][j-1]);
            if(i+j==n){
                res=max(res,dp[i][j]);
                break;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 34580
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

// 二分累乗 O(funcの計算量*logE)
template<typename T>
T binpow(T x, ll e, function<T(T,T)> func=[](T a, T b){return a*b%MOD;}, T d=1) {
  T ret = d, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = func(p, p); e /= 2;}
    else {ret = func(ret, p); e--;}
  }
  return ret;
};

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

  ll n, k;
  cin >> n >> k;
  vector<vector<ll>> a(n, vector<ll>(n));
  REP(i, n) REP(j, n) cin >> a[i][j];

  using mat = vector<vector<ll>>;
  auto f = [&n](mat a, mat b) {
    mat ret(n, vector<ll>(n));
    REP(i, n) REP(j, n) REP(k, n) {
      (ret[i][j] += a[i][k] * b[k][j] % MOD) %= MOD;
    }
    return ret;
  };

  mat d(n, vector<ll>(n));
  REP(i, n) d[i][i] = 1;
  mat ret = binpow<mat>(a, k, f, d);
  ll ans = 0;
  REP(i, n) REP(j, n) (ans += ret[i][j]) %= MOD;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
from collections import deque
n=int(input())
a=list(map(int,input().split()))
d=deque(a)
tmp=[d[0]]
d.popleft()
ans=1
while d:
    t=tmp[-1]-tmp[0]
    if len(tmp)==1 or t==0:
        tmp.append(d.popleft())
    elif t>0 and d[0]>=tmp[-1]:
        tmp.append(d.popleft())
    elif t<0 and d[0]<=tmp[-1]:
        tmp.append(d.popleft())
    else:
        ans+=1
        tmp=[d.popleft()]
print(ans)

Measured memory_bytes: 14508
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define range(x,l,r) (l<=x && x<r)
#define chmax(a,b) ((a) = max((a),(b)))
using namespace std;

const int dy[] = {0,1,0,-1}, dx[] = {1,0,-1,0};
int dp[50][50][4][1<<12];
int vis[1<<12];

inline bool visit(int bit){
  //if(vis[bit]>=0)return vis[bit];
  int y=0, x=0;
  rep(i,6){
    int d = bit&3; bit>>=2;
    y += dy[d], x += dx[d];
    if(y==0 && x==0)return vis[bit] = true;
  }
  return vis[bit] = false;
}

int main(){
  int h,w,k;
  string g[50];
  cin >> h >> w >> k;
  rep(i,h)cin >> g[i];

  memset(vis,-1,sizeof(vis));
  memset(dp,-1,sizeof(dp));
  dp[0][0][0][0] = isdigit(g[0][0])?(int)(g[0][0]-'0'):0;

  rep(rev,k+1){
    rep(y,h)rep(x,w){
      if(g[y][x] == '#')continue;
      rep(bit,1<<12){
	if(dp[y][x][rev][bit]<0)continue;

	rep(d,4){
	  int ny = y+dy[d], nx = x+dx[d];
	  if(!range(ny,0,h) || !range(nx,0,w))continue;
	  if(g[ny][nx] == '#')continue;

	  int nbit = ((bit<<2)|d) & ((1<<12)-1);
	  int item = isdigit(g[ny][nx])?(int)(g[ny][nx]-'0'):0;
	  if(visit(nbit))item = 0;

	  if(d<2){
	    chmax(dp[ny][nx][rev][nbit], dp[y][x][rev][bit] + item);
	  }else if(rev!=k){
	    chmax(dp[ny][nx][rev+1][nbit], dp[y][x][rev][bit] + item);
	  }
	}
      }
    }
  }

  int res = 0;
  rep(bit,1<<12)chmax(res, dp[h-1][w-1][k][bit]);
  cout << res << endl;
}

Measured memory_bytes: 161236