akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, n;
ll dp[400][400][134];
bool circ[400][400][400];
int cnt[410][410];
int A[410], B[410];

int f(int i, int j, int t) {
	return max(N - 3 * (n - t) - cnt[i][j], 0);
}

void solve() {
	cin >> N; n = N / 3;
	rep(i, 0, N) {
		cin >> A[i]; A[i]--;
	}
	rep(i, 0, N) {
		cin >> B[i]; B[i]--;
	}
	if(A[0] == B[0]) {
		cout << "0\n";
		return;
	}
	rep(i, 0, N + 1) {
		rep(j, 0, N + 1) {
			if(j - 1 >= 0) {
				rep(k, 0, N) circ[i][j][k] = circ[i][j - 1][k];
				circ[i][j][B[j - 1]] = 1;
			}
			else if(i - 1 >= 0) {
				rep(k, 0, N) circ[i][j][k] = circ[i - 1][j][k];
				circ[i][j][A[i - 1]] = 1;
			}
			cnt[i][j] = accumulate(circ[i][j], circ[i][j] + N, 0);
		}
	}
	rep(i, 0, N) {
		dp[i][0][1] = 1; dp[0][i][1] = 1;
	}
	rep(i, 1, N) {
		rep(j, 1, N) {
			rep(k, 1, n + 1) {
				if(!circ[i][j][A[i]] && !circ[i][j][B[j]] && A[i] != B[j]) {
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] * f(i + 1, j + 1, k) % mod;
				}
				ADD(dp[i][j][k], (dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k] + mod) % mod);
				//debug(i, j, k, dp[i][j][k], dp[i][j - 1][k], dp[i - 1][j][k], S[i][j][k]);
			}
		}
	}
	ll res = dp[N - 1][N - 1][n];
	// debug(res);
	rep(i, 0, n) {
		MUL(res, (N - i * 3 - 1) * (N - i * 3 - 2) % mod);
	}
	cout << res << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



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

int main() {
	int A[2], K;
	cin >> A[0] >> A[1] >> K;
	for (int i = 0;i < K;++ i) {
		A[i & 1] >>= 1;
		A[i & 1 ^ 1] += A[i & 1];
	}
	cout << A[0] << " " << A[1];
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

実際にシミュレーションするだけ。O(K)
*/

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

int main() {
    string s,t;
    cin >> s >> t;
    int ans = 0;
    rep(i,s.length()){
        if(s.at(i) != t.at(i)){
            ans++;
        }
    }

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

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

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

    for (int i = 0; i < a + b + 1; i++) {
        if (i == a) {
            if (s[i] != '-') {
                cout << "No" << endl;
                return 0;
            }
        }
        else {
            if (s[i] < '0' || s[i] > '9') {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}


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

int mm[105];
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(0);   
#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif

  int n,k;
  cin>>n>>k;
  int x;
  for(int i=1;i<=k;i++)
  {
    cin>>x;
    int y;
    for(int j=0;j<x;j++)
    {
      cin>>y;
      mm[y]++;
    }
  }
  int cnt=0;
  for(int i=1;i<=n;i++)
  {
    if(mm[i]==0)
      cnt++;
  }
  cout<<cnt;

}

Measured memory_bytes: 3652
#include<cstdio>
#define neko 100010
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-(i)))
int n,L,a[neko],now,nowi;
int main()
{
	scanf("%d%d",&n,&L);
	f(i,1,n)scanf("%d",&a[i]);
	if(n==1)return puts("Possible"),0;
	f(i,1,n-1)if(now<a[i]+a[i+1])now=a[i]+a[i+1],nowi=i;
	if(now>=L)
	{
		puts("Possible");
		f(i,1,nowi-1)printf("%d\n",i);
		rf(i,n-1,nowi+1)printf("%d\n",i);
		printf("%d\n",nowi);
		return 0;
	}
	else return puts("Impossible"),0;
}

Measured memory_bytes: 1152
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
using namespace std;
int main(){
    int n;
    double r;
    scanf("%d\n",&n);
    r=n;
    printf("%.10lf\n",2*r*3.1415926535);
    return 0;
}

Measured memory_bytes: 3828
M = 2019

L, R = map(int, input().split())

if R-L >= M or L%M >= R%M:
    ans = 0
else:
    ans = M
    L, R = L%M, R%M
    for i in range(L, R+1):
        for j in range(i+1, R+1):
            ans = min(ans, (i*j)%M)

print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll a;
    ld b;
    ll c = 0;
    cin >> a >> b;
    while(c < b * 100 - 0.5) c++;
    cout << a * c / 100 << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Measured memory_bytes: 3748
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(read())
B = sorted(A)
d = {B[i] : i for i in range(N)}
ans = sum((d[A[i]] ^ i) & 1 for i in range(N)) // 2
print(ans)

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

using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
	
	int A,B; cin>>A>>B;
	if (abs(A-B) % 2 == 1) {
	    cout << "IMPOSSIBLE" << endl;
	    return 0;
	}
	auto ans = (A+B)/2;
	cout << ans << endl;
	
    return 0;
}


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

#define ll long long int
ll mod=1e9+7;

// vector<ll> g[200005];
// ll vis[200005];
// queue<ll> q;
// ll level[200005];

// void dfs(ll i)
// {
//     vis[i] = 1;
//     for(ll j=0;j<g[i].size();j++)
//     {
//         ll child = g[i][j];
//         if(vis[child] == 0)
//         {
//             dfs(child);
//         }
//     }
// }

// void bfs(ll i)
// {
//     vis[i] = 1;
//     while(!q.empty())
//     {
//         ll top = q.front();
//         ll len_adj = g[top].size();
//         ll j;
//         for(j=0;j<len_adj;j++)
//         {
//             ll v = g[top][j];
//             if(vis[v]==0)
//             {
//                 vis[v]=1;
//                 q.push(v);
//                 level[v] = level[top] + 1;
//             }
//         }   
//         q.pop();
//     }
// }

vector<ll> DecToBinary(ll num,ll trailing_zero, ll nbits)
{
    vector<ll> bits;
    while(num > 0)
    {
        bits.push_back(num%2);
        num /= 2;
    }

    if(trailing_zero == 1)
    {
        while(bits.size() < nbits)
        {
            bits.push_back(0);
        }
    }

    return bits;
}

long long int BinaryToDec(vector<ll> bits)
{
    ll number = 0;
    ll i;
    for(i=bits.size()-1;i>=0;i--)
    {
        number += (bits[i] * (long long)pow((ll)2 , i));
    }
    return number;
}



ll modular_exponentiation(ll base, ll power)
{
    ll ans = 1;
    base = base % mod;
    while (power > 0)
    {
        if (power & 1)
        {
            ans = (ans * base) % mod;
        }

        power /= 2;
        base = (base * base) % mod;
    }
    return ans;
}



int main()
{
    /* Faster input ouput */
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    /* To read input from a file and output to a file */
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    
    ll t = 1;
    // cin >> t;
    while(t--)
    {        
        ll n,i,j,x,y;
        cin >> x >> y;
        // ll arr[n];

        // for(i=0;i<n;i++)
        // {
        //     cin >> arr[i];
        // }

        ll b = (y - (2*x)) / 2;
        ll a = x - b;

        if(a>=0 && b >= 0)
        {
            if(a+b == x && (2*a+4*b == y))
            {
                cout << "Yes\n";
                return 0;
            }
        }

        cout << "No\n";

    }

    
    
}

Measured memory_bytes: 3720
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

LL solve(const vector<LL> &a, bool plus){
    LL res = 0;
    LL sum = 0;
    int n = a.size();
    REP(i, n){
        sum += a[i];
        if(plus){
            if(sum <= 0){
                res += 1LL - sum;
                sum = 1LL;
            }
        }else{
            if(sum >= 0){
                res -= -1LL - sum;
                sum = -1LL;
            }
        }
        //cout << sum << endl;
        plus = !plus;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    vector<LL> a(n);
    REP(i, n)cin >> a[i];
    LL res = min(solve(a, true), solve(a, false));
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
const int MOD = 1e9 + 7;
 
 
signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  int N, M;
  cin >> N >> M;
  int A[N];
  rep(i,N) cin >> A[i];
  rep(i,N) A[i] = A[i]/2;
 
  int ans = 1;
  rep(i,N){
    ans = ans * A[i] / __gcd(ans,A[i]);
    if(ans > M){
      cout << 0 << endl;
      return 0;
    }
  }
  for(int i=0;i<N;i++){
    if((ans/A[i]) % 2 == 0){
      cout << 0 << endl;
      return 0;
    }
  }
 
  cout << ((M/ans)+1)/2 << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0; i<n;i++)
#define MAX 105000
using namespace std;

int main (){
	/*for(int k = 1; k<MAX;k++)
	{
		if(PrimeCheck(v[k+1]))
		{
			//cout << v[k+1] << " ";
			v2[d] = v[k+1];
			d++;
		}
	}
	//rep(i,d) cout << v2[i] << " ";
	//cout << d << endl;*/
	int number;
	while(cin >> number,number)
	{


		int counter = 0;
		vector<bool>v(MAX+1,0);
		vector<int>v2(MAX,0);
		rep(i,MAX)
			v[i+1] = true;
		long long answer = 0;
		int lim = (int)sqrt(number);
		int d = 0;
//		cout << lim <<" ";
		for(int i = 2; i<MAX; i++)
		{
			if(v[i])
			{
				for(int j = 2; j <MAX/i;j++)
				{
					v[j*i]  = false;
					//cout << " " << i << "i*j=  " << i*j;
				}
				v2[d] = i;
				d++;
			}	
		}
		//rep(i,number) cout << v[i+1] << " ";
		for(int i = 2; i<MAX+1;i++)
		{	
			if(v[i])
			{
				answer+=i;
				counter++;
				//cout << " " << i;
				if(counter == number)
					break;
			}
			
		}
		cout  /*<< " answer is "*/ << answer << endl;
	    
	}
	return 0;
}

Measured memory_bytes: 3508
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<array<int, 3>> v(N);
  for (int i = 0; i != N; ++i) {
    cin >> v[i][0] >> v[i][1] >> v[i][2];
  }

  auto &[x, y, h] = *find_if(begin(v), end(v), [](auto &t) { return t[2]; });
  for (int cx = 0; cx <= 100; ++cx) {
    for (int cy = 0; cy <= 100; ++cy) {
      auto H = h + abs(x - cx) + abs(y - cy);
      if (all_of(begin(v), end(v), [&](auto &t) {
            return t[2] == max(H - abs(t[0] - cx) - abs(t[1] - cy), 0);
          })) {
        cout << cx << " " << cy << " " << H << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i < e; i++)
#define rrep(i, s, e) for(int i = s; i > (s)-(e); i--)
#define pr(s) std::cout << s << std::endl
#define prb(s) std::cout << s
using namespace std;



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


  int a, b, c;
  cin >> a >> b >> c;

  if (a >= b && a >= c) pr(b+c);
  else if (b >= a && b >= c) pr(a+c);
  else pr(a+b);


  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char st[500];

int main()
{
	scanf("%s", st + 1);
	int n = strlen(st + 1);
	int ans = 0;
	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if ((j - i) & 1)
			{
				int l = i;
				int r = (i + j + 1) / 2;
				bool flag = true;
				while (r <= j)
				{
					if (st[l] != st[r])
					{
						flag = false;
						break;
					}
					l++;
					r++;
				}
				if (flag && j - i + 1 != n)
				{
					ans = max(ans, j - i + 1);
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
    int d[2000000];
    int k,x,i;
    
    scanf("%d%d",&k,&x);
    for(i=(x+1000000)-k+1;i<(x+1000000)+k;i++){
    d[i]=-1000000+i;
    }
    for(i=(x+1000000)-k+1;i<(x+1000000)+k;i++){
    printf("%d ",d[i]);}
    printf("\n");
    return 0;
    }

Measured memory_bytes: 2176
#include <iostream>
#include <map>

using namespace std;

int main() {
    int s;
    map<int, bool> mp;

    cin >> s;

    int crnt = s, next;
    mp[crnt] = true;
    for (int i=2;;i++) {
        if (crnt%2) next = 3*crnt+1;
        else next = crnt/2;

        if (mp.count(next)) {
            cout << i << endl;
            return 0;
        }

        mp[next] = true;
        crnt = next;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    int n;
    cin >> n;
    vector<vector<int>> f(n, vector<int>(10));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 10; ++j) cin >> f[i][j];
    }
    vector<vector<int>> p(n, vector<int>(11));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= 10; ++j)    cin >> p[i][j];
    }
    int ans = -INF;
    for(int bit = 1; bit < (1 << 10); ++bit){
        vector<int> PopPos;
        for(int i = 0; i < 10; ++i){
            if((bit >> i) & 1)  PopPos.emplace_back(i);
        }
        vector<int> c(n, 0);
        for(int x : PopPos){
            for(int i = 0; i < n; ++i){
                if(f[i][x]) ++c[i];
            }
        }
        int S = 0;
        for(int i = 0; i < n; ++i){
            S += p[i][c[i]];
        }
        chmax(ans, S);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int f(int a[],int n,int k){
   int dp[n];
   dp[n-1]=0;
   
   for(int i=n-2;i>=0;i--){
       dp[i]=INT_MAX;
       for(int j=1;j<=k;j++){
           
           if(i+j>=n-1)
           dp[i]=min(dp[i],dp[n-1]+abs(a[i]-a[n-1]));
           else
           dp[i]=min(dp[i],dp[i+j]+abs(a[i]-a[i+j]));
       }
   }
   return dp[0];
}



int main() {
    

        int n,k;
        cin>>n>>k;
        int a[n];
        for(int i=0;i<n;i++)
        cin>>a[i];
        
        cout<<f(a,n,k)<<endl;
        
    
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  vector<int> a;
  for(int i=0;i<s.size();i++){
    if(s[i]=='0'){
      a.push_back(0);
    }
    else if(s[i]=='1'){
      a.push_back(1);
    }
    else{
      if(a.size()!=0){
      a.pop_back();
      }
    }
  }
    for(int i=0;i<a.size();i++){
      cout<<a.at(i);
    }
  
    cout<<"\n";
  
  return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
    long long x;
    mint(long long x=0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    
    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    
    vll p(n, 0), q(n, 0);

    // pはブロック内
    rep(i, n) {
        for (int j = i+1; j < n; ++j) {
            if (a[i] > a[j]) p[i]++;
        }
    }
    // qはブロック外
    rep(i, n) {
        rep(j, n) {
            if (a[i] > a[j]) q[i]++;
        }
    }

    mint ans;
    mint mk(k);
    rep(i, n) {
        ans += mint(p[i]) * mk + mint(q[i]) * mk * (mk - mint(1)) / 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n, k = gets.chop.split(" ").map(&:to_i)
ans =
    Array.new(n) do
      Array.new(2)
    end
n.times do |i|
  ans[i][0], ans[i][1] = gets.chop.split(" ").map(&:to_i)
end

#ans.sort!
ans.sort_by! { |i| i[0]}

n.times do |i|
  k = k - ans[i][1]
  if k <= 0
    puts ans[i][0]
    break
  end
end


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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)
#define	INF (1<<29)
//536870912

#define	MOD 1000000007

int	main() {
	int N, L;
	cin >>N >>L;
	vector<string> S;
	for (int i=0; i<N; i++) {
		string SS;
		cin >>SS;
		S.push_back(SS);
	}
	sort(S.begin(), S.end());
	for (int i=0; i<N; i++)
		cout <<S.at(i);
	cout <<endl;
	return 0;
}



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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
typedef long long ll;
typedef pair<int, int> pii;
const int inf=1010001000;
const ll  INF=1001000100010001000;
const int mod=(int)1e9+7;

int main(){
    int n;
    cin>>n;
    int dp[10][10]={0};
    rep(i,1,n+1){
        if(i%10==0)continue;
        string s=to_string(i);
        dp[s.at(0)-'0'][i%10]++;
    }
    int ans=0;
    rep(i,1,10){
        rep(j,1,10){
            ans+=dp[i][j]*dp[j][i];
        }
    }
    cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 256
///スマホコーディング
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
typedef long long ll;
const int inf=1e9;
int main(){
  set<string> se;
  int n; cin>>n;
  string ans="Yes";
  char pre;
  rep(i,0,n){
    string w; cin>>w;
    if(se.find(w)!=se.end())ans="No";
    if(i!=0&&pre!=w[0])ans="No";
    se.insert(w);
    pre=w[w.size()-1];
  }
  cout<<ans<<endl;
  return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  ll n;cin>>n;
  vector<ll> x(n);
  rep(i, n)cin>>x[i];
  ll result = INF;
  rep(i, 100){
    ll t = 0;
    rep(j, n){
      t += (x[j]-i)*(x[j]-i);
    }
    result = min(result, t);
  }
 
  cout<<result; 

  return 0;
}

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

int main() {
  int r,d,x;
  cin >> r >> d >> x;
 rep(i,10){
   x=r*x-d;
     cout << x <<endl;
 }
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main{
// taking inputs
static BufferedReader s;
static String read() throws IOException{String line="";while(line.length()==0){line=s.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
// ends
static int value(String s1){return Integer.parseInt(s1);}

public static void main(String[] args) throws  IOException{
        s=new BufferedReader(new InputStreamReader(System.in));;
       StringBuilder sb=new StringBuilder();
       BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
       int[] a=int_arr();
       int[] p=int_arr();
       long sum=0,tmp=0;
       for(int i=0;i<a[1];i++){sum+=p[i];}tmp=sum;
       	for(int i=a[1];i<a[0];i++){
       		tmp+=p[i]-p[i-a[1]];
       		sum=Math.max(sum,tmp);
       	}
       	double xx=(double)(sum+a[1])/2;
        out.write(xx+"");
        out.flush();
  }
}


Measured memory_bytes: 51064
n, x, y = map(int, input().split())

min_diff = [[-1] * (n+1) for _ in range(n+1)]
for st in range(1, n+1):
    for go in range(st, n+1):
        min_diff[st][go] = go-st
        if x < st and go < y:
            min_diff[st][go] = min(min_diff[st][go], (st-x)+(y-go)+1)
        elif x >= st and go < y:
            min_diff[st][go] = min(min_diff[st][go], (x-st)+(y-go)+1)
        elif x < st and go >= y:
            min_diff[st][go] = min(min_diff[st][go], (st-x)+(go-y)+1)
        else:
            min_diff[st][go] = min_diff[st][go] - (y-x) + 1

#print(min_diff)

ans = [0] * (n+1)
for i in range(n+1):
    for j in range(n+1):
        ans[min_diff[i][j]] += 1

for i in range(1, n):
    print(ans[i])

Measured memory_bytes: 79836
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++);
#define _GLIBCXX_DEBAC
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/

using namespace std;

int gcd(int a, int b) {
	int c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

int sort_greater(int m,int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(),greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
		return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t,sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}
map<string, int> memo;


int main() {
	//sort(a.begin(),a.end());
	long long a, b, c;
	cin >> a >> b >> c;
	if (c-a-b>0&&4*a*b<(c-a-b)*(c-a-b)) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}









Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,N) for(int i = 0;i < (int)(N);i++)
int main(){
  string s;
  cin>>s;
  string ans="Sunny";
  if(s=="Sunny") ans="Cloudy";
  if(s=="Cloudy") ans="Rainy";
  cout<<ans<<endl;
}


Measured memory_bytes: 256
n = int(input())
L = list(map(int,input().split()))

li = [0]

for i in range(n):
    li.append(li[i]+ L[i])

sumL = sum(L)
#print(sumL)
ans = 10**10
for i in range(1,n):
    diff = abs(li[i] - (sumL - li[i]))
    #print(diff,li[i],sumL-li[i])
    ans = min(ans,diff)        
print(ans)

Measured memory_bytes: 30832
def insertionSort(A, n, g):
    cnti = 0
    for i in range(g, n):
        v = A[i]
        j = i-g
        while (j >= 0 and A[j] > v):
            A[j + g] = A[j]
            j -= g
            cnti += 1
        A[j+g] = v
    return cnti
def shellSort(A,n):
    cnt = 0
    G = [1]
    h = 1
    for k in range(int(n**0.33333333)+1):
        h = 3*h + 1
        if (h <= n and len(G) < 100):
            G.append(h)
        elif(len(G) == 100):
            break    
    G.reverse()
    m = len(G)
    for i in range(m):
        cnt += insertionSort(A, n, G[i])
    print(m)
    for i in range(m):
        if (i == m-1):
            print('{}'.format(G[i]), end = '')
        else:
            print('{}'.format(G[i]), end = ' ')
    return cnt
        
        
        
n = int(input())
nlist = []
for i in range(n):
    x = int(input())
    nlist.append(x)
    
c = shellSort(nlist,n)
print()
print(c)
for i in nlist:
    print(i)


Measured memory_bytes: 45532
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2050
int n,a[N];
int K,Q,b[N],c[N],ans=1<<30,tot;
void add(int l,int r) {
	int i;
	for(i=l;i<=r;i++) b[i]=a[i];
	sort(b+l,b+r+1);
	for(i=l;i<=r-K+1;i++) c[++tot]=b[i];
}
void solve(int x) {
	int i,lst=1; tot=0;
	for(i=1;i<=n;i++) {
		if(a[i]<x) {
			if(lst<=i-1) add(lst,i-1);
			lst=i+1;
		}
	}
	if(lst<=n) add(lst,n);
	sort(c+1,c+tot+1);
	if(tot<Q) return ;
	ans=min(ans,c[Q]-c[1]);
}
int main() {
	int i;
	scanf("%d%d%d",&n,&K,&Q);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) {
		solve(a[i]);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 128
/*
    _____
  .'|||||'.
 /  >   <  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
    |||||
*/

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
struct part{
LL v;
int id;
};
struct part1{
int x,y;
LL v;
};
bool cmp(struct part a, struct part b)
{
    return(a.v<b.v);
}
int f[100010];
int find1(int x)
{
    if (f[x]==x) return(x); else f[x]=find1(f[x]);
    return(f[x]);
}
bool cmp1(struct part1 a, struct part1 b)
{
    return(a.v<b.v);
}
struct part x[100010],y[100010];
struct part1 a[200010];
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
    LL xx,yy;
    scanf("%lld%lld",&xx,&yy);
    x[i].v=xx;
    x[i].id=i;
    y[i].v=yy;
    y[i].id=i;
}
sort(x+1,x+1+n,cmp);
sort(y+1,y+1+n,cmp);
int o=0;
for (int i=1;i<=n-1;i++)
{
    o++;
    a[o].x=x[i].id;
    a[o].y=x[i+1].id;
    a[o].v=x[i+1].v-x[i].v;
}
for (int i=1;i<=n-1;i++)
{
    o++;
    a[o].x=y[i].id;
    a[o].y=y[i+1].id;
    a[o].v=y[i+1].v-y[i].v;
}
sort(a+1,a+1+o,cmp1);
for (int i=1;i<=n;i++)
    f[i]=i;
int k=0;
LL ans=0;
for (int i=1;i<=o;i++)
{
    int fa=find1(a[i].x);
    int fb=find1(a[i].y);
    if (fa!=fb)
    {
        f[fa]=fb;
        ans+=a[i].v;
        k++;
    }
    if (k==n-1) break;
}
printf("%lld\n",ans);
    return(0);
}


Measured memory_bytes: 7040
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

#if 1
int gcd1(int x,int y){
  if(x<y) swap(x,y);
  //xの方が常に大きい
  while(y>0){
    int r=x%y;
    x=y;
    y=r;
  }
  return x;
}

int gcd2(int x,int y){
  if(x<y) swap(x,y);
  if(y==0) return x;
  return gcd2(y,x%y);
}

int lcm(int x,int y){
  return int(x*y/gcd1(x,y));
}
#endif

int main(){
  int x,y;cin >> x >> y;
  cout << gcd2(x,y) << endl;
}



Measured memory_bytes: 3084
#include<stdio.h>
int a[3], t;
int main(void){
  scanf("%d%d%d", a, a+1, a+2);
  if(a[0]<a[1]){t=a[1]; a[1]=a[0]; a[0]=t;}
  if(a[0]<a[2]){t=a[2]; a[2]=a[0]; a[0]=t;}
  printf("%ld\n", (long)(a[0]&1)*a[1]*a[2]);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define fi first
#define se second
#define pb push_back
#define read(type, ...)type __VA_ARGS__; macro_scan(__VA_ARGS__);
#define debug(...)cerr<<"["<<#__VA_ARGS__<<"] : ",deb(__VA_ARGS__);

using namespace std;

template<typename T> void macro_scan(T& t){cin>>t;};
template<typename F, typename ...R>void macro_scan(F& f , R& ...r){
  cin>>f;macro_scan(r...);
}

void deb(){
    cerr<<endl;
}
template<typename T , typename... t>
void deb(T a , t...b){
    cerr<<a<<",";
    deb(b...);
}
template<typename T>
void dev(vector<T>v){
    int c = 0;
    for(auto i : v){
        cerr<<i<<" ";
        c++;
    }
    cerr<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t; cin>>t;for(;t--;)done();
    read(double , a , b , c , d);
    double pi = acos(-1);
    double angle = 0.5 * (60.0 * c - 11.0 * d);
    double ans = a * a + b * b -  2 * a * b * cos(angle * pi / 180.0);
    printf("%.10f\n", sqrt(ans));

}
//@01928419790ar epic games ar7iq r7e

Measured memory_bytes: 4244
#include<stdio.h>
#include<stdlib.h>
int B[1000];
int top;

int main()
{
  int x,y;
  char b[100];
  int top=0;


  while(scanf("%s",b)!=EOF) {
     
      if(b[0]=='+'){
	x=pop();
	y=pop();
	push(x + y);
      }
      else if(b[0]=='-'){
	x=pop();
	y=pop();
	push(y-x);
      }
      else if(b[0]=='*'){
	x=pop();
	y=pop();
	push(x*y);
      }
      else {
	push(atoi(b));
      }
    }

      printf("%d\n",pop());

      return 0;
}


void push(int a){
  B[++top]=a;
}

int pop(){
  top--;
  return B[top+1];
}



Measured memory_bytes: 2108
//
// Created by munaiyi on 2020/3/18.
//
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int pri[maxn / 10], t;
bool flag[maxn];
int num[maxn];

void init() {
    memset(flag, 0, sizeof(flag));
    t = 0;
    for (int i = 2; i < maxn; i++) {
        if (!flag[i]) {
            pri[t++] = i;
        }
        for (int j = 0; j < t && i * pri[j] < maxn; j++) {
            flag[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

long long fast(long long num, int ci) {
    long long ans = 1;
    while (ci) {
        if (ci & 1) ans = ans * num % mod;
        num = num * num % mod;
        ci = ci >> 1;
    }
    return ans;
}

void update(int &tnum, int p, unordered_map<int, int> &mp, long long &sum) {
    int tmp = mp[p];
    int cnt = 0;
    while (tnum % p == 0) {
        tnum /= p;
        cnt++;
    }
    if (cnt > tmp) {
        while (tmp < cnt) {
            sum = sum * p % mod;
            tmp++;
        }
        mp[p] = tmp;
    }
}

int main() {
    init();
    int n;
    scanf("%d", &n);
    unordered_map<int, int> mp;
    long long sum = 1;
    for (int i = 0; i < n; i++) {
        scanf("%d", num + i);
        int tnum = num[i];
        for (int j = 0; j < t; j++) {
            if (tnum % pri[j] == 0) {
                update(tnum, pri[j], mp, sum);
            }
            if (pri[j] * pri[j] > tnum) break;
        }
        if (tnum > 1) {
            update(tnum, tnum, mp, sum);
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += sum * fast(num[i], mod - 2) % mod;
    }
    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}



Measured memory_bytes: 3840
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<i64> p(n);
  for (i64 i = 0; i < n; i++)
    cin >> p[i];
  vector<i64> tmp = p;
  sort(p.begin(), p.end());
  bool ans = (tmp == p);
  for (i64 i = 0; i < n; i++)
    for (i64 j = i + 1; j < n; j++)
    {
      swap(p[i], p[j]);
      if (p == tmp)
        ans = true;
      swap(p[i], p[j]);
    }
  if (ans)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
def Csum(a,x):
    b,c=[0],0
    for i in range(len(a)):
        if a[i]==x:
            c+=1
        b.append(c)
    return b

n=int(input())
s=input()
a,b,w,e=Csum(s,'W'),Csum(s,'E'),s.count('W'),s.count('E')
a.append(w)
b.append(e)
ans=n
for i in range(1,n+1):
    ans=min(ans,e+a[i-1]-b[i])
print(ans)

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


int main(){
    string S;
    cin>>S;
    string A[]={"Sunny","Cloudy","Rainy"};
    if(S=="Sunny")cout<<A[1]<<endl;
    else if(S=="Cloudy")cout<<A[2]<<endl;
    else cout<<A[0]<<endl;
    return 0;
}


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

int main(){ 
string s;
cin>>s;
int A=0;
size_t n = s.length();
for(int i=0; i<n; i++){
if(s[i]!=s[n-1-i]){
A++;
}
}
cout<<A/2<<endl;
}


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

// 入力
int n, W;
int weight[110], value[110];

// DPテーブル
int dp[110][10010];

int main() {
	cin >> n >> W;
	for (int i = 0; i < n; ++i) cin >> value[i] >> weight[i];

	// DP初期条件: dp[0][w] = 0
	for (int w = 0; w <= W; ++w) dp[0][w] = 0;

	// DPループ
	for (int i = 0; i < n; ++i) {
		for (int w = 0; w <= W; ++w) {
			if (w >= weight[i]) dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]);
			else dp[i + 1][w] = dp[i][w];
		}
	}

	cout << dp[n][W] << endl;
}


Measured memory_bytes: 7052
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
#include <cassert>
#include <memory>
using namespace std;
typedef long long ll;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

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

    int i1 = 1;
    int i2 = M + 2;

    for (int diff = M; diff >= 1; diff--) {
        if (diff % 2 == M % 2) {
            cout << i1 << " " << i1 + diff << endl;
            i1++;
        }
        else {
            cout << i2 << " " << i2 + diff << endl;
            i2++;
        }
    }

    return 0;
}


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

using namespace std;

using ll=long long;

int main(){
    int n;cin>>n;
    vector<ll>v(3*n);
    for(int i=0;i<3*n;++i){
        cin>>v[i];
    }
    sort(v.begin(),v.end(),greater<ll>());
    ll ans=0;
    for(int i=0;i<2*n;++i){
        if(i%2)ans+=v[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
# -*- coding: utf-8 -*-

n = int(input())
d, x = map(int,input().split())
a = [0] * n
for i in range(n):
    a[i] = int(input())
choco = [0] * d
for i in range(n):
    for j in range(100):
        if a[i]*j+1 > d:
            break
        choco[a[i]*j] += 1

print(x + sum(choco))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
#include <math.h>
#include<algorithm>
using namespace std;
#define INFTY 2000000000
#define MAX 120000

struct drink{
  long long value,bottle;
};


drink d[MAX],L[MAX],R[MAX];

void merge(long long left,long long mid,long long right){
  long long n1=mid-left;
  long long n2=right-mid;
  for(long long i=0;i<n1;i++){
    L[i]=d[left+i];
  }
  for(long long i=0;i<n2;i++){
    R[i]=d[mid+i];
  }
  L[n1].value=INFTY;
  R[n2].value=INFTY;
  long long i=0;
  long long j=0;
  for(int k=left;k<right;k++){
    if(L[i].value<=R[j].value){
      d[k]=L[i];
      i++;
    }else{
      d[k]=R[j];
      j++;
    }
  }

}

void mergeSort(long long left,long long right){
  if(left+1<right){
    long long  mid=(left+right)/2;
    mergeSort(left,mid);
    mergeSort(mid,right);
    merge(left,mid,right);
  }
}

int main(){
  long long  n,m;
  cin>>n>>m;
  for(long long i=0;i<n;i++){
    scanf("%d%d",&d[i].value,&d[i].bottle);
  }
  mergeSort(0,n);

  long long sum=0,count=0;
  long long k=0;
  while(true){
    if(d[k].bottle+count>=m){
      sum+=(m-count)*d[k].value;
      break;
    }
    sum+=d[k].bottle*d[k].value;
    count+=d[k].bottle;
    k++;
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 4480
using System;
using System.Collections.Generic;
using System.Linq;

namespace D
{
    public struct Node
    {
        public int left;
        public int right;
        public Tree tree;
    }

    public class Tree
    {
        internal Node[] nodes;

        public Tree(int nodes)
        {
            this.nodes = new Node[nodes + 1];
            for (int i = 1; i < nodes + 1; i++)
            {
                this.nodes[i].left = -1;
                this.nodes[i].right = -1;
                this.nodes[i].tree = this;
            }
        }

        public void AddChilden(int id, int left, int right)
        {
            nodes[id].left = left;
            nodes[id].right = right;
        }

        public void Postorder(int node,ref List<int> list)
        {
            if (nodes[node].left != -1) Postorder(nodes[node].left,ref list);
            if (nodes[node].right != -1) Postorder(nodes[node].right,ref list);
            list.Add(node);
        }

        public int Analyze(IEnumerable<int> preList, IEnumerable<int> inList)
        {
            if (preList.Count() == 0) return -1;
            var node = preList.First();
            var index = inList.ToList().IndexOf(node);
            var left = Analyze(preList.Skip(1).Take(index), inList.Take(index));
            var right = Analyze(preList.Skip(1 + index), inList.Skip(1 + index));
            AddChilden(node, left, right);
            return node;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var preList = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var inList = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var tree = new Tree(n);
            var list = new List<int>();
            tree.Postorder(tree.Analyze(preList, inList),ref list);
            Console.WriteLine(string.Join(" ",Array.ConvertAll(list.ToArray(),(s)=>s.ToString())));
        }
    }
}

Measured memory_bytes: 10140
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)      x.begin(), x.end()
#define rep(i,n)    for (i64 i = 0; i < (n); ++i)
#define reps(i,s,t) for (i64 i = (s); i <= (t); ++i)
#define repr(i,s,t) for (i64 i = (s); i >= (t); --i)

#ifdef DBG
#define trace(...) _trace(#__VA_ARGS__, __VA_ARGS__);
#else
#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,1) : 0;}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a ? (a=b,1) : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &vec) {
    rep(i, vec.size()) os << vec[i] << (i+1 == vec.size() ? "" : " ");
    return os;
}

template<class T, class U>
ostream& operator<< (ostream &os, const pair<T, U> &p) {
    return os << p.first << ' ' << p.second;
}

template <class T>
void _trace(const char *s, T&& x)
{
    clog << '{';
    while(*s != '0' && *s != ',') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void _trace(const char *s, Head&& head, Tail&&... tail)
{
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    _trace(s, std::forward<Tail>(tail)...);
}
// }}} End Header

signed main()
{
    // ios::sync_with_stdio(false); cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;

    cout << ((a <= c && c <= b) ? "Yes" : "No") << "\n";

    return 0;
}


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

public class Main {
	static int INF = 1000000000;
	int cityAmount;
	int root[][];
			
	public Main(){
		Scanner scan = new Scanner(System.in);
		
		while(scan.hasNext()){
			cityAmount = scan.nextInt();
			if(cityAmount == 0) break;
			
			root = new int[cityAmount+1][cityAmount+1];
			for(int[] l:root)Arrays.fill(l, INF);
			
			//Create root map 
			for(int i = 0; i < cityAmount ;i++){
				int a = scan.nextInt();
				int b = scan.nextInt();
				int c = scan.nextInt();
				root[a][b] = c;
				root[b][a] = c;
			}
			
			for ( int k = 0; k < cityAmount+1; k++ ){
		        for ( int i = 0; i < cityAmount+1; i++ ){
		            for ( int j = 0; j < cityAmount+1; j++ ){
		            	root[i][j] = Math.min( root[i][j], root[i][k] + root[k][j] );
		            }
		        }
		    }

			int cityNo = 0;
			int sum = INF;
			for ( int i = 0; i < cityAmount+1; i++ ){
	            int tmpSum = 0;
				for ( int j = 0; j < cityAmount+1; j++ ){
	            	if(i != j && root[i][j] != INF){
	            		tmpSum += root[i][j];
	            	}
	            }

	            if(tmpSum != 0 && sum > tmpSum){
	            	sum = tmpSum;
	            	cityNo = i;
	            }
	        }
			System.out.println(cityNo +" "+ sum);
			
		}
	}
	
	public static void main(String[] args) {
		new Main();
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
int p[100010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> p[i];
    p[i]--;
  }
  int ans = 0;
  for (int i = 0; i + 1 < N; i++) {
    if (p[i] != i) continue;
    swap(p[i], p[i + 1]);
    ans++;
  }
  if (p[N - 1] == N - 1) ans++;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
using namespace std;

typedef int64_t ll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define vll vector<ll>
#define all(v) v.begin(), v.end()


int main() {

	ll L;
	cin >> L;
	ll rest = L;

	ll next = 1ll;
	ll maxN = 0;

	vector<vector<ll>> ans;
	for (ll i = 0; next * 2 <= L; ++i) {
		rest -= next;
		ans.push_back(vector<ll>({ i + 1, i + 2, next }));
		ans.push_back(vector<ll>({ i + 1, i + 2, 0 }));
		next <<= 1;
		if (maxN < i + 2) maxN = i + 2;
	}
	rest--;

	while (rest > 0) {
		ll tbit = -1;
		for (ll i = 0;; ++i) {
			if (rest >> i & 1) {
				tbit = i;
				break;
			}
		}
		ll diff = 1 << tbit;
		ans.push_back(vector<ll>({ tbit + 1, maxN, next }));
		rest -= diff;
		next += diff;
	}

	cout << maxN << " " << ans.size() << endl;
	for (auto e : ans) cout << e[0] << " " << e[1] << " " << e[2] << endl;
}


Measured memory_bytes: 256