akhauriyash/Code-Regression huggingface dataset:
// Header {{{
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}

signed main() {
    ll n,ans=0,even=0,odd=0;
    map<ll,ll> mp;
    cin>>n;
    rep(i,0,n){
        ll x;
        cin>>x;
        mp[x]++;
    }
    for(auto e: mp){
        (e.second%2==0?even:odd)++;
    }
    ans += even + odd;
    if (even%2==1)
        ans--;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6528
n = int(input())
div = []
ans = []

for i in range(1,int(n**0.5)+2):
    if n%i == 0:
        div.append(i)
        div.append(n//i)

for i in div:
    if i == 1:
        continue
    k = n
    while k%i == 0:
        k//=i
    if k%i== 1:
        ans.append(i)
        
n -= 1

for i in range(1,int(n**0.5)+2):
    if n%i == 0:
        ans.append(i)
        ans.append(n//i)
        
print(len(set(ans)) - 1)

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

bool dislike[10];
int N, K;

void solve(){
    REP(res, N, 10*N + 1) {
        int p = res;
        bool flg = true;
        while(p > 0) {
            int d = p%10; p /= 10;
            if(dislike[d]) {flg = false; }
        }
        if(flg) { cout << res << endl; return; }
    }
}

int main()
{
    cin >> N >> K;
    REP(i, 0, K) { int d; cin >> d; dislike[d] = true; }
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#define INF 1e+9
using namespace std;
 
int main(){
	int n,m;
	int cost[100][100],cost2[100][100];
	bool used[100][100] = {};
	cin >> n >> m;
	for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) cost[i][j] = INF;
	for(int i = 0;i < n;i++) cost[i][i] = 0;
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		cost[a - 1][b - 1] = c;
		cost[b - 1][a - 1] = c;
		used[a - 1][b - 1] = true;
		used[b - 1][a - 1] = true;
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			cost2[i][j] = cost[i][j];
		}
	}
	for(int k = 0;k < n;k++){
		for(int j = 0;j < n;j++){
			for(int i = 0;i < n;i++){
				cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j]);
			}
		}
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			for(int k = 0;k < n;k++){
				if(cost[i][j] - cost[i][k] == cost2[k][j]) {
					used[j][k] = false;
					used[k][j] = false;
				}
			}
		}
	}
	int res = 0;
	for(int i = 0;i < n - 1;i++){
		for(int j = i + 1;j < n;j++){
			if(used[i][j]) res++;
		}
	}
	cout << res << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

int main() {
	int n[5];
	for (int i = 0; i < 5; ++i) { cin >> n[i]; }

	int res = 0;
	int x = 0;
	for (int i = 0; i < 5; ++i) {
		int t = ((n[i] + 9) / 10) * 10;
		res += t;
		x = max(x, t - n[i]);
	}

	cout << res - x << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 10;
char s[N];
int main(){
    scanf("%s",s);
    int n = strlen(s);
    long long ans = 0;
    for(int i=0;i<n;i++){
        int x = 0, y = 0;
        while(i+x<n&&s[i+x]=='<') x++;
        while(i+x+y<n&&s[i+x+y]=='>') y++;
        i += x + y - 1;
        if(x>y) swap(x,y);
        y++;
        ans += 1ll * x * (x-1) / 2 + 1ll * y * (y-1) / 2;
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 768
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        int x = (int)(Math.round(n / 1.08));
        int ans1 = (int)(x * 1.08);
        int ans2 = (int)((x + 1) * 1.08);
        int ans3 = (int)((x - 1) * 1.08);
        if(n == ans1){
        	System.out.println(x);
        }else if(n == ans2){
            System.out.println(x + 1);
        }else if(n == ans3){
            System.out.println(x - 1);
        }else{
        	System.out.println(":(");
        }
    }
} 

Measured memory_bytes: 35696
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ACirclePond solver = new ACirclePond();
        solver.solve(1, in, out);
        out.close();
    }

    static class ACirclePond {
        public void solve(int testNumber, FastReader s, PrintWriter w) {
            w.println(2 * Math.PI * s.nextInt());
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 25668
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int C = scan.nextInt();

		double theta = C >= 90 ? Math.toRadians(180 - C) : Math.toRadians(C);
		
		double h = Math.sin(theta) * b;

		double w = C >= 90 ? a + b * Math.cos(theta) : a - b * Math.cos(theta);
		double c = Math.sqrt(h * h + w * w);
		double L = a + b + c;
		double S = h * a / 2.0;

		System.out.println(S);
		System.out.println(L);
		System.out.println(h);
		
		scan.close();
	}

}

Measured memory_bytes: 17180
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  ll x;
  cin >> x;
  ll ans = 0;
  if (x > 6) {
    ll temp = x % 11;
    ans = (x-temp)*2 / 11; //必ず割り切れる
    if (temp <= 6 && temp > 0) ans++;
    else if (temp > 6) ans += 2;
  }
  else ans = 1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var a, b int
	var ans string
	fmt.Scan(&a, &b)
	if a == b {
		ans = "Draw"
	} else if a == 1 {
		ans = "Alice"
	} else if b == 1 {
		ans = "Bob"
	} else {
		if a < b {
			ans = "Bob"
		} else {
			ans = "Alice"
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int X = scan.nextInt();
        int Y= scan.nextInt();

        int kame = 0;

        for(; kame <= X; kame++) {
            int tsuru = X-kame;
            if(tsuru*2 + kame*4 == Y){
                os.println("Yes");
                return;
            }
        }

        os.println("No");

    }
}

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

int main() {
	int N;
	long X, L[51] = {1}, P[51] = {1}, ans = 0;
	cin >> N >> X;
	for (int i = 0; i < N; ++i) {
		L[i + 1] = L[i] * 2 + 3;
		P[i + 1] = P[i] * 2 + 1;
	}
	while (N >= 0) {
		if (N == 0) {
			++ans;
			break;
		}
		if (X == 1) break;
		if (X == L[N]) {
			ans += P[N];
			break;
		}
		if (X == L[N] / 2 + 1) {
			ans += P[N - 1] + 1;
			break;
		}
		if (X > L[N] / 2 + 1) {
			ans += P[N - 1] + 1;
			X -= L[N - 1] + 2;
		}
		else --X;
		--N;
	}
	cout << ans;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

inline void input() {}
template <class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }

inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}
// }}} End Header

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

    var(int, N, K);
    unordered_map<int, int> cnt;

    rep(i, N) {
        var(int, a);
        cnt[a] += 1;
    }

    vector<int> kkk;
    for (const auto  &e : cnt) {
        kkk.push_back(e.second);
    }

    sort(all(kkk), greater<>());

    i64 ans = 0;
    while(kkk.size() > K) {
        ans += kkk.back();
        kkk.pop_back();
    }

    print(ans);

    return 0;
}


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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
template<typename T>
ll sz(priority_queue<T, vector<T>> &pq) {return (ll)pq.size(); }
template<typename T>
ll sz(priority_queue<T, vector<T>, greater<T>> &pq) {return (ll)pq.size(); }
ll sz(string &s) {return (ll)s.size(); } 
ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b; }
bool checkindex(ll i,ll n){ return (i < n && i >= 0); }

int main(){
    ll n,m;
    cin >> n >> m;
    vector<ll> a(n),b(m);
    rep(i,0,n) cin >> a[i];
    rep(i,0,m) cin >> b[i];
    vector<ll> c(n+m-1);

    c = convolution<998244353>(a,b);

    rep(i,0,n+m-1){
        cout << c[i] << ((i == n+m-2)?"\n":" ");
    }
    return 0;
}



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

#define vi vector<int>
#define vl vector<long long>
#define vvi vector< vector<int> >
#define vvl vector< vector<ll> >
#define vp vector<P>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPD(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORD(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define INF 1e18
#define INFTY 1e9
const int mod = 998244353;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

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

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

//cout << fixed << setprecision(10) << y << endl;
struct edge {int to, cost;};
vector< vector<edge> > es;
const int MAX_N = 10010;

int main() {
    int n, s;
    cin >> n >> s;
    vi a(n);
    REP(i, n) cin >> a[i];
    ll dp[n+1][s+1];
    REP(i, n+1) {
        REP(j, s+1) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;
    //dp[i][j]:i番目までのaが使える時の総和がjになる場合の数
    REP(i, n) {
        REP(j, s+1) {
            dp[i+1][j] += 2*dp[i][j];
            dp[i+1][j] %= mod;
            //dp[i+1][j]にはTに今見ている要素を入れない場合
            //Tには今見ている要素を加え、T=TU{a[i]}とするが、Uには加えない場合
            //を入れる
            if (j+a[i] <= s) {
                dp[i+1][j+a[i]] += dp[i][j];
                dp[i+1][j+a[i]] %= mod;
            }
        }
    }
    cout << dp[n][s] << endl;
    return 0;
}

Measured memory_bytes: 73972
//感谢Factorio
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;
int n,D1,D2;
int a[1005][1005];
void Doit(int dist){
    int c=0;
    while (dist%4==0){
        dist/=4;
        c++;
    }
    if (dist%2==0){
        for (int i=0;i<2*n;i++){
            for (int j=0;j<2*n;j++){
                if ((i>>c)&1){
                    a[i][j]=1;
                }
            }
        }
    }
    else{
        for (int i=0;i<2*n;i++){
            for (int j=0;j<2*n;j++){
                if (((i>>c)+(j>>c))&1){
                    a[i][j]=1;
                }
            }
        }
    }
}
int main() {
    cin>>n>>D1>>D2;
    Doit(D1);
    Doit(D2);
    int cnt=0;
    for (int i=0;i<2*n;i++){
        for (int j=0;j<2*n;j++){
            if (a[i][j]==0){
                cnt++;
                cout<<i<<" "<<j<<endl;
                if (cnt==n*n){
                    return 0;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	int n;
	cin >> n;
	int a[n];
	REP(i,n) cin >> a[i];
	sort(a, a + n, greater<int>());
	int alice = 0, bob = 0;
	REP(i,n){
		if(i %  2 == 0) alice += a[i];
		else bob += a[i];
	}
	cout << alice - bob << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)n; ++i)
#define print(x) (cout << x << endl)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<pair<int, int> > vii;


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
 
  int n, cnt = 0, endA = 0, startB = 0, both = 0;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    for (size_t p = s[i].find("AB"); p != string::npos; p = s[i].find("AB", p + 1)) {
      cnt++;
    } 
    if (s[i].back() == 'A' && s[i].front() == 'B') both++;
    else if (s[i].back() == 'A') endA++;
    else if (s[i].front() == 'B') startB++;
  }
  
  if (both == 0) {
    cout << cnt + min(endA, startB) << endl;
  } else{
    if (endA + startB == 0) {
      cout << cnt + both - 1 << endl;
    } else {
      cout << cnt + both + min(endA, startB) << endl;
    }
  }
  
  
  // cout << "Case #" << C++ << ": " << cur_max << endl;  


}



Measured memory_bytes: 768
//Author: AnandRaj doubleux
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a,b;
	cin>>a>>b;
	bool ans=false;
	for(int i=0;i<10000;i++)
	{
		if(i*8/100==a&&i*10/100==b)
		{
			cout<<i<<endl;
			ans=true;
			break;
		}
	}
	if(!ans) cout<<-1<<endl;
}		

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;

template<typename T>void chmax(T &a,T b){a=max(a,b);}
template<typename T>void chmin(T &a,T b){a=min(a,b);}
using namespace std;

void solve(){
	int n;
	ll c,k;
	cin>>n>>c>>k;
	vector<ll>t(n);
	ll minv=1e9+5,maxv=0;
	rep(i,n){
		cin>>t[i];
		minv=min(minv,t[i]);
		maxv=max(maxv,t[i]);
	}
	sort(t.begin(),t.end());
	ll cnt=1,ans=0;
	ll cmp=t[0];
	for(int i=0;i<n;++i){
		while(cnt<c&&i<n){
			if(abs(cmp-t[i+1])<=k){
				++cnt;
				++i;
			}
			else {
				break;
			}
		}
		cmp=t[i+1];
		cnt=1;
		++ans;
	}
	cout<<ans<<endl;
}

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


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

int main(){
  int A[3][3];
  int N;
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      cin >> A[i][j];
    }
  }

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

  /* solver */
  int punch[3][3];
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      for(int k=0; k<N; k++){
        if(A[i][j] == B[k]){
          punch[i][j] = 1;
          break;
        }else{
          punch[i][j] = 0;
        }
      }
    }
  }

  int x_count = 0;
  int y_count = 0;
  int n_count = 0;
  int result = 0;

  for(int i=0; i<3; i++){
    int x_count = 0;
    int y_count = 0;
    for(int j=0; j<3; j++){
      x_count += punch[i][j];
      y_count += punch[j][i];
    }
    if(x_count == 3 || y_count == 3){
      result += 1;
    }
  }
  if(punch[0][0]+punch[1][1]+punch[2][2] == 3){
    result += 1;
  }else if(punch[0][2] + punch[1][1] + punch[2][0] == 3){
    result += 1;
  }
  if(result > 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
///https://agc020.contest.atcoder.jp/tasks/agc020_c?lang=en

#include<bits/stdc++.h>
#define i64 long long
#define inf 1000000000000000000
using namespace std;

int ara[2001];
bitset<2001*2001>bset;//[2];
int main()
{
    int n;
    scanf("%d",&n);

    int sum=0,mx=0;
    for(int i=1; i<=n; i++)
        scanf("%d",&ara[i]);


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

    for(int i=1; i<=n; i++)
    {
        sum+=ara[i];
        mx=max(mx,ara[i]);
    }

    int avg=(sum+2-1)/2, last=mx*n;

    bset[0]=1;
    for(int i=1; i<=n; i++)
        bset= bset | (bset<<ara[i]);


    for(int i=avg; i<=last; i++)
    {
        if(bset[i]==1)
        {
            printf("%d\n",i);
            return 0;
        }
    }


    return 0;
}


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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

//===

//const ll mod = static_cast<int>(1e9 + 7);



int main() {
	string S;
	cin >> S;

	int N = static_cast<int>(S.size());
	Vi ans(N);


	Vi RL;
	RL.push_back(0);
	int mode = 0;  // 0 : R, 1 : L
	for (int i = 1; i < N; ++i) {
		if (mode == 0) {
			if (S[i] == 'L') {
				RL.push_back(i);
				mode = 1 - mode;
			}
		}
		else {
			if (S[i] == 'R') {
				RL.push_back(i);
				mode = 1 - mode;
			}
		}
	}

	RL.push_back(N);

	for (int i = 0; i < RL.size() - 2; i += 2) {
		int R_left = RL[i];
		int R_right = RL[i + 1] - 1;
		int L_left = RL[i + 1];
		int L_right = RL[i + 2] - 1;
		int margin = L_left;

		ans[R_right] += (R_right - R_left + 1 + 1) / 2;
		ans[R_right] += (L_right - L_left + 1) / 2;
		ans[L_left] += (L_right - L_left + 1 + 1) / 2;
		ans[L_left] += (R_right - R_left + 1) / 2;
	}

	for (int i = 0; i < N - 1; ++i) {
		cout << ans[i] << " ";
	}
	cout << ans[N - 1] << endl;
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
#define mod 1000000007
using namespace std;

int main(){
    int a,b,ans;
    cin >> a >> b;
    if(a>9 || b>9)ans = -1;
    else ans = a*b;

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

H, W, K = [int(x) for x in input().strip().split()]

k = 1
pre = []
first = 0
for h in range(H):
    dk = -1
    S = input().strip()
    ans = []
    if '#' not in S:
        if len(pre) == 0:
            first += 1
            continue
        else:
            print(*pre)
            continue
    for s in S:
        if s == '#':
            dk += 1
        ans.append(k + max(0, dk))
    else:
        print(*ans)
        if first:
            for _ in range(first):
                print(*ans)
            first = 0
        k += max(0, dk) + 1
        pre = ans[:]
    


Measured memory_bytes: 4080
#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()
{
	string s,t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	if (s < t) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,col[100005],flag=0,cnt,hd[100005],ans1=0,ans2=0;
struct node{
	int to,next;
}e[200005];
void addedge(int x,int y){
	e[++cnt].next=hd[x];
	e[cnt].to=y;
	hd[x]=cnt;
}
void dfs(int x,int fa,int color){
	col[x]=color;
	for(int i=hd[x];i;i=e[i].next){
		int to=e[i].to;
		if(to==fa) continue;
		if(col[to]&&color==col[to]) flag=1; 
		if(!col[to]) dfs(to,x,3-color);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		addedge(a,b);
		addedge(b,a);
	}
	for(int i=1;i<=n;i++) if(!col[i]) dfs(i,0,1);
	if(flag){
		cout<<n*(n-1)/2-m<<endl;
		return 0;
	}
	else{
		for(int i=1;i<=n;i++){
			if(col[i]==1) ans1++;
			else if(col[i]==2) ans2++;
		}
		cout<<ans1*ans2-m<<endl;
	}
	return 0;
}


Measured memory_bytes: 9572
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll H,W;
    cin >> H >> W;
    if (H==1 || W==1)
    {
        cout << 1 << "\n";
        return 0;
    }
    ll ans = (H/2) *( ((W+1)/2) + (W/2));
    if (H%2) ans += ((W+1)/2);
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e6 + 100;
typedef long long ll;

//prime次数 
int num[N], n;
inline void divide(int x) {
	for(int i = 2; i <= x/i; i++) {
		if(x % i == 0) {
			num[i]++;
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) num[x]++;
}
int main() {
	
	cin >> n;
	
	int MaxNum = 0;
	for(int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		divide(x); 
		
		MaxNum = max(MaxNum, x);
	}
	
	int f1 = 0;
	for(int i = 2; i <= MaxNum; i++) {
		if(num[i] >= n) {
			puts("not coprime");
			return 0;
		}
		if(num[i] > 1) {
			f1 = 1;
			//return 0; 
		}
	}
	if(f1) puts("setwise coprime");
	else puts("pairwise coprime");
	return 0;
}

Measured memory_bytes: 7660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<ll> v(n), ans(n, 0);
	for(ll&x: v) cin >> x;
	if(n == 1){
		cout << v[0] << endl;
		return 0;
	}
	ans[n - 2] = abs(v[n - 1] - v[n - 2]);
	for(int i = n - 3;i >= 0; --i)
		ans[i] = min(ans[i + 2] + abs(v[i] - v[i + 2]), ans[i + 1] + abs(v[i] - v[i + 1]));
	cout << ans[0] << endl;
	return 0;
}


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

int main(){
string a;
cin >>a;
if(a.size()%2){
int b;
b=a.size();
b--;
for(int i=b;i>=0;i--)
{

cout << a[i];
}
cout<< endl;
return 0;
}
cout <<a << endl;
return 0;
}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace ABC140
{
    public class Program
    {

        #region templete

        private static void WL(string s) { WriteLine(s); }

        /// <summary>
        /// 最小公倍数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        static long Gcd(long a, long b)
        {
            var v = new[] { a, b };
            while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
            return v[0];
        }
        /// <summary>
        /// 最小公約数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }

        public static void Main(string[] args)
        {
            new Program().Solve();
            ReadLine();
        }

        #endregion

        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();
            var a = cin.ArrayInt(n);
            var b = cin.ArrayInt(n);
            var c = cin.ArrayInt(n-1);
            int ans = b[a[0] - 1];
            for (int i = 1; i < n; i++)
            {
                ans += b[a[i] - 1];
                if (a[i] - a[i - 1] == 1) ans += c[a[i - 1] - 1];
            }
            WL($"{ans}");
        }

    }
}


#region console in

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

#endregion

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    if (v.size() == 0) return os << "]";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    lint A, B;
    cin >> A >> B;
    cout << (B - 1) / (A - 1) + ((B - 1) % (A - 1) == 0 ? 0 : 1) << "\n";
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

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

    bool ok = true;
    rep(i, N) if (A[i] % 2 == 0 && A[i] % 3 && A[i] % 5) ok = false;

    if (ok) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif


//改造
typedef long long int ll;
using namespace std;


//ここから編集する

ll max(ll a,ll b){
    return (a < b)? b : a;
}

int main() {
    int N, W;
    cin >> N >> W;

    ll w0, v0;
    cin >> w0 >> v0;

    vector<ll> V[4];

    V[0].push_back(v0);

    REP(i, 1, N) {
        ll w, v;
        cin >> w >> v;
        V[w - w0].push_back(v);
    }

    vector<ll> sumV[4];
    REP(i, 0, 4) {
        sort(V[i].begin(), V[i].end(), greater<int>());

        sumV[i].push_back(0);
        REP(j, 0, V[i].size()) {
            sumV[i].push_back(V[i][j] + sumV[i][j]);
        }
    }



//    REP(i,0,N+1){
//        REP(j,i,N+1){
//            REP(k,j,N+1){
//                int l = N - i - j - k;
//
//            }
//        }
//    }
    ll max_v = -1;
    for (int i = 0; i <= N && i <= V[0].size(); i++) {
        for (int j = 0; i + j <= N && j <= V[1].size(); j++) {
            for (int k = 0; i + j + k <= N && k <= V[2].size(); k++) {
                for (int l = 0; i + j + k + l <= N && l <= V[3].size(); l++) {
                    if (i * w0 + j * (w0 + 1) + k * (w0 + 2) + l * (w0 + 3) <= W){
                        max_v = max(max_v,sumV[0][i] + sumV[1][j] + sumV[2][k] + sumV[3][l]);
                    }
                }
            }
        }
    }
    cout << max_v << endl;

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
#include<map>//map
using namespace std;
typedef long long LL; 
typedef pair<LL,LL> P;//Pでpair<-,->を表す。
const LL MAX=2000010;
const LL MOD=1000000007;
typedef map<LL,LL>::iterator Itr;

int main()
{ 
    LL n,a,b,c;
    cin>>n>>a>>b>>c;
    LL s[n+1];
    for(int i=0;i<n;i++){
        string S;
        cin>>S;
        if(S=="AB"){s[i]=0;}
        if(S=="AC"){s[i]=1;}
        if(S=="BC"){s[i]=2;}
    }
    s[n]=0;
    vector <string> v;
    for(int i=0;i<n;i++){
        if(s[i]==0){
            if(a==b&&a==0){cout<<"No"<<endl;return 0;}
            if(a>b){a--;b++;v.push_back("B");}
            else if(a<b){a++;b--;v.push_back("A");}
            else{
                if(s[i+1]==2){a--;b++;v.push_back("B");}
                else{a++;b--;v.push_back("A");}
            }
        }
        else if(s[i]==1){
            if(a==c&&a==0){cout<<"No"<<endl;return 0;}
            if(a>c){a--;c++;v.push_back("C");}
            else if(a<c){a++;c--;v.push_back("A");}
            else{
                if(s[i+1]==2){a--;c++;v.push_back("C");}
                else{a++;c--;v.push_back("A");}
            }
        }
        else{
            if(b==c&&b==0){cout<<"No"<<endl;return 0;}
            if(b>c){b--;c++;v.push_back("C");}
            else if(b<c){b++;c--;v.push_back("B");}
            else{
                if(s[i+1]==1){b--;c++;v.push_back("C");}
                else{b++;c--;v.push_back("B");}
            }
        }
    }
    cout<<"Yes"<<endl;
    for(int i=0;i<n;i++){
        cout<<v[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 8248
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    C = list(int(input()) for _ in range(n))
    MAX_C = max(C)

    dp = [0] * (n + 1)
    dp[0] = 1
    dp2 = [-1] * (MAX_C + 1)
    for i in range(n):
        c = C[i]
        if dp2[c] >= 0 and dp2[c] < i - 1:
            dp[i + 1] = dp[i] + dp[dp2[c] + 1]
        else:
            dp[i + 1] = dp[i]
        dp[i + 1] %= mod
        dp2[c] = i

    print(dp[-1] % mod)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 30244
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

struct Edge {
  int to;
  int cost;
  Edge(int t, int c) : to(t), cost(c) {}
};

typedef vector< vector<Edge> > AdjList;
AdjList graph;
vector<int> dist;
vector<int> par;

bool bellman_ford(int n, int s){ // n: number of edges, s: source
  bool negloop = false;
  dist = vector<int>(n, inf);
  dist[s] = 0;
  for(int i=0; i<n; i++){
    for(int v=0; v<n; v++){
      for(int k=0; k<graph[v].size(); k++){
        Edge e = graph[v][k];
        if(dist[v] != inf && dist[e.to] > dist[v] + e.cost){
          dist[e.to] = dist[v] + e.cost;
          par[e.to] = v;
          if(i == n - 1) {
            dist[e.to] = -inf;
            negloop = true;
          }
        }
      }
    }
  }
  return negloop;
}

vector<int> buildPath(int t) {
  vector<int> path;
  for(int u=t; u>=0; u=par[u])
    path.push_back(u);
  reverse(path.begin(), path.end());
  return path;
}

int main() {
  int N, M, P;
  cin >> N >> M >> P;
  graph = AdjList(N);
  par = vector<int>(N, -1);
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    graph[a].push_back(Edge(b, -(c-P)));
  }
  bool ret = bellman_ford(N, 0);
  if(ret) {
    vector<int> path;
    for(int u=N-1; u>=0&&path.size()<N; u=par[u])
      path.push_back(u);
    reverse(path.begin(), path.end());
    for(int p: path) {
      if(dist[p] == -inf) {
        cout << -1 << endl;
        return 0;
      }
    }
  }
  cout << max(0, -dist[N-1]) << endl;
  return 0;
}



Measured memory_bytes: 512
program prob4
    implicit none
    integer::N,M,i,j,ans
    integer,allocatable::X(:)
    read(*,*) N,M
    allocate(X(M))
    read(*,*) X
    ans = 0
    if(N < M) then
        call heapsort(M,X)
        do i = 1, M-1
            X(i) = X(i+1) - X(i)
        end do
        X(M) = 0
        call heapsort(M,X)
        do i = 1, M - N + 1
            ans = ans + X(i)
        end do
    end if

    write(*,*) ans
    deallocate(X)
    stop
    contains
    subroutine heapsort(n,array)
        implicit none
        integer,intent(in) :: n
        integer,intent(inout) :: array(1:n)
       
        integer ::i,k,j,l
        double precision :: t
       
        if(n.le.0)then
           write(6,*)"Error, at heapsort"; stop
        endif
        if(n.eq.1)return
      
        l=n/2+1
        k=n
        do while(k.ne.1)
           if(l.gt.1)then
              l=l-1
              t=array(L)
           else
              t=array(k)
              array(k)=array(1)
              k=k-1
              if(k.eq.1) then
                 array(1)=t
                 exit
              endif
           endif
           i=l
           j=l+l
           do while(j.le.k)
              if(j.lt.k)then
                 if(array(j).lt.array(j+1))j=j+1
              endif
              if (t.lt.array(j))then
                 array(i)=array(j)
                 i=j
                 j=j+j
              else
                 j=k+1
              endif
           enddo
           array(i)=t
        enddo
      
        return
    end subroutine heapsort
end program

Measured memory_bytes: 3572
#include <iostream>
using namespace std;
int main()
{
    long long a , b , k , sa , ans;
    cin >> a >> b >> k;
    if(a <= k){
        sa = k - a;
        a = 0;
        if(sa >= b){
            b = 0;
        }else{
            b -= sa;
        }
    }else{
        a -= k;
    }
    cout << a << " " << b << endl;
    return(0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  
int main() {
  ll n;
  cin >> n;
  bool a=false;
  rep(i,30){
    rep(j,20){
      if(4*i+7*j==n){
        a=true;
      }
    }
  }
  if(a){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}

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

using namespace std;

typedef long long ll;

bool comp(const vector<ll> &a, const vector<ll> &b){
  return a[0] < b[0];
}

int main(){
  ll N, M, a, b;
  ll ans = 0;
  cin >> N >> M;
  int p = 0;
  vector<vector<ll>> drinks;
  for (int i=0; i<N; i++){
    cin >> a >> b;
    drinks.emplace_back(vector<ll>{a, b});
  }
  
  sort(drinks.begin(), drinks.end(), comp);

  while (M > 0){
	if (drinks[p][1] >= M){
      ans += drinks[p][0] * M;
      M = 0;
    }
    else{
      ans += drinks[p][0] * drinks[p][1];
      M -= drinks[p][1];
      p++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 6836
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let a=read::<i32>();
    let b=read::<i32>();
    let c=read::<i32>();
    let d=read::<i32>();
    println!("{}",a*c+(if a>b{(a-b)*(d-c)}else{0}))
}

Measured memory_bytes: 4352
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <utility>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <math.h>
#include <stdio.h>
#include <deque>

using namespace std;

#define REP(i,n,m) for( long long int i = (n); i < (m); i++ )
#define REV(v) for (auto itr = v.rbegin(); itr != v.rend(); itr++)
#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define SORT(v) sort( ALL(v) );
#define LAST(v) v[v.size()-1]
#define ZERO(a) memset(a,0,sizeof(a));
#define MINUS(a) memset(a,-1,sizeof(a));
#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 pi pair<int, int>
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define IIN(a) int a; cin >> a;
#define LIN(a) ll a; cin >> a;
#define SIN(a) string a; cin >> a;
#define VL(v,n) vector<ll> v(n);
#define Read_VL(v,n) vector<ll> v(n);REP(i,0,n)cin>>v[i];
#define sumV(v,n) Vl(acm,n) REP(i,0,n) acm[i] = v[i] + ( i == 0 ? 0 : acm[i - 1]);
#define EPS (1e-10)
#define INF 1000000000000LL

void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}


template<class T=ll>struct Graph{
	int n;
	vector<vector<tuple<ll,T>>>edge;
	Graph(int N=1):n(N){edge.resize(n);}
	void add(ll f,ll t,T c,bool d=false){
		edge[f].emplace_back(t,c);
		if(!d)edge[t].emplace_back(f,c);
	}
	void view(){
		REP(i,0,n)for(auto&e:edge[i])
			puta(i,"=>",get<0>(e),", cost :",get<1>(e));
	}
};


bool length_cmp( string &a, string &b ){
  return a.size() < b.size();
}

ll StoLL( string s )
{
	ll num=0;
  REP( i, 0, s.size() ){
    num = num * 10 + ( s[i] ^ 48 );
  }
  return num;
}

ll CtoLL( char c )
{
	if( 'a' <= c && c <= 'z'){
		return (ll)( c ^ 96 ) ;
	}
	else if( 'A' <= c && c <= 'Z'){
		return (ll)( c ^ 64 );
	}
  return 0;
}

ll MOD=1000000007;
ll dx[4] = { 1, 0, -1, 0 };
ll dy[4] = { 0, 1, 0, -1 };
//I ASCII code: '0' = 48; 'A' = 65; 'a' = 97

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    SIN(s)
    string ret;
    REP( i, 0, s.size() ){
      if( s[i] == 'A' ){
        ret.PB('T');
      }else if( s[i] == 'T' ){
        ret.PB('A');
      }else if( s[i] == 'C' ){
        ret.PB('G');
      }else if( s[i] == 'G' ){
        ret.PB('C');
      }
    }
    puta( ret );

    return 0;
}


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

int d[22][22][22][22];
int main() {
    int h, w;
    cin >> h >> w;
    for(int i = 0; i < h; i++)
        for(int ii = 0; ii < w; ii++)
            for(int j = 0; j < h; j++)
                for(int jj = 0; jj < w; jj++)
                    d[i][ii][j][jj] = i == j && ii == jj ? 0 : 1e8;
    string s[22];
    for(int i = 0; i < h; i++)
        cin >> s[i];
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(s[i][j] == '#')
                continue;
            if(i && s[i - 1][j] == '.')
                d[i][j][i - 1][j] = d[i - 1][j][i][j] = 1;
            if(j && s[i][j - 1] == '.')
                d[i][j][i][j - 1] = d[i][j - 1][i][j] = 1;
        }
    }
    for(int j = 0; j < h; j++)
        for(int jj = 0; jj < w; jj++)
            for(int i = 0; i < h; i++)
                for(int ii = 0; ii < w; ii++)
                    for(int k = 0; k < h; k++)
                        for(int kk = 0; kk < w; kk++)
                            d[k][kk][i][ii] = d[i][ii][k][kk] =
                                min(d[i][ii][k][kk],
                                    d[i][ii][j][jj] + d[j][jj][k][kk]);
    int r = 0;
    for(int i = 0; i < h; i++)
        for(int ii = 0; ii < w; ii++)
            for(int k = 0; k < h; k++)
                for(int kk = 0; kk < w; kk++)
                    if(d[i][ii][k][kk] < 1e7)
                        r = max(r, d[i][ii][k][kk]);
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
const int INF = 2000000000;

int n;
priority_queue<int> a;

int main(){
  cin>>n;
  rep(i, n){
    int tmp;
    cin >> tmp;
    a.push(tmp);
  }
  int dif = INF;
  int ans_1 = a.top(), ans_2;
  a.pop();
  while(!a.empty()){
    int tmp = a.top();
    a.pop();
    if(abs(2*tmp - ans_1) < dif){
      ans_2 = tmp;
      dif = 2*tmp - ans_1;
    }
  }
  cout << ans_1 <<" "<<ans_2<<endl;
}

Measured memory_bytes: 892