akhauriyash/Code-Regression huggingface dataset:
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll Rcnt=0;
    rep(i,n){
        if(s[i]=='R'){
            Rcnt++;
        }
    }
    ll res=0;
    rep3(i,Rcnt,n){
        if(s[i]=='R'){
            res++;
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 3760
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> b = new ArrayList<Integer>();
		int a = sc.nextInt();
		int sum = 0;
		for(int i = 0; i < a; i++){
			int c = sc.nextInt();
			b.add(c);
		}
		Collections.sort(b);
		for(int i = 0; i < a; i++){
			int d = b.get(i);
			if(i == a-1){
				d = d/2;
			}
			sum += d;
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 23124
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    int N; cin>>N;
    vector<int>h(N+1,0);
    rep(i,N)cin>>h[i];
    int ans=0;
    rep(i,100){
        rep(j,N){
            if(h[j]>0){
                h[j]--;
                if(h[j+1]==0)ans++;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import scala.collection.mutable.ListBuffer
import scala.io.StdIn

object Main extends App {
  
  sealed abstract class Node {
    val key: Int
    var prev:Node
    var next: Node
  }

  case class Elements(key: Int, var prev:Node, var next: Node) extends Node {
    override def toString: String = s"Elements($key)"
  }

  case object MyNil extends Node{
    val key: Int = 0
    var prev: Node = MyNil
    var next: Node = MyNil
    override def toString: String = s"MyNil"
  }

  def insert(newVal: Int): Unit = {
    var x = Elements(newVal, MyNil, MyNil.next)
    MyNil.next.prev = x
    MyNil.next = x
  }

  def listSearch(searchVal: Int): Node = {
    var target = MyNil.next
    while(target.key != searchVal && target != MyNil){
      target = target.next
    }
    target
  }
  
  // nullを設定可能か？
  def deleteNode(target: Node): Unit = {
    if(target != MyNil){
      target.prev.next = target.next
      target.next.prev = target.prev
    }
  }

  def deleteFirst(): Unit = deleteNode(MyNil.next)

  def deleteLast(): Unit = deleteNode(MyNil.prev)

  def deleteKey(target: Int): Unit = deleteNode(listSearch(target))


  val n = StdIn.readLine().trim.toInt
  (0 until n).foreach{ _ =>
    val cmd = StdIn.readLine().trim.split(' ')
    if (cmd(0) == "deleteFirst") deleteFirst()
    else if(cmd(0) == "deleteLast") deleteLast()
    else if(cmd(0) == "insert") insert(cmd(1).toInt)
    else if(cmd(0) == "delete") deleteKey(cmd(1).toInt)
  }
  
  //println(commandList)
  //val buff = ArrayBuffer.empty[Int]
  val buff = ListBuffer.empty[Int]
  var current = MyNil.next
  while(current != MyNil){
    buff += current.key
    current = current.next
  }
  println(buff.mkString(" "))
}


Measured memory_bytes: 469632
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

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

const ll LINF = 1001002003004005006LL;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int ans = 0;
    rep(i,n) {
        if (((i+1)%2)!=0 && (a[i]%2)!=0) ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
using ll = long long;
using namespace std;
ll n,k,s=0,a[550],b[550],ans=0;
ll f(ll p){
    ll s2=0,s3=0;
    rep(i,0,n){b[i]=a[i]%p;s2+=b[i];}
    sort(b,b+n);
    rep(i,0,n-s2/p)s3+=b[i];
    return s3<=k?p:0;
}
int main(){
    cin>>n>>k;
    rep(i,0,n) {cin>>a[i];s+=a[i];}
    for(ll p=1;(p*p)<=s;p++) if(s%p==0){
        ans=max(ans,f(p));
        ans=max(ans,f(s/p));
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=-1;
char grid[2010][2010];
vector<int> row[2010],col[2010];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		col[i].push_back(0);
	for(int i=1;i<=n;i++)
	{
		row[i].push_back(0);
		for(int j=1;j<=m;j++)
		{
			cin>>grid[i][j];
			if(grid[i][j]=='#')
			{
				row[i].push_back(j);
				col[j].push_back(i);
			}
		}
		row[i].push_back(m+1);
	}
	for(int i=1;i<=m;i++)
		col[i].push_back(n+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int r1=*(lower_bound(row[i].begin(),row[i].end(),j))\
			-*(lower_bound(row[i].begin(),row[i].end(),j)-1)-1;
			int r2=*(lower_bound(col[j].begin(),col[j].end(),i))\
			-*(lower_bound(col[j].begin(),col[j].end(),i)-1)-1;
			ans=max(ans,r1+r2-1);
		}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 38400
#include<iostream>
#include<map>
#include<utility>
#include<cmath>

#define ll long long

using namespace std;

int main(){


	ll n,d,x,y;
	cin >> n >> d;

	map<pair<int,int>,int>mp;

	while(n--){
		cin >> x >> y;
		if(mp[make_pair(x,y)]!=0)
			mp[make_pair(x,y)]++;
		else{
			double dist = ceil(sqrt(pow(x,2)+pow(y,2)));
			if(dist<=d)
				mp[make_pair(x,y)]++;
		}
	}

	int cnt=0;

	for(auto itr:mp)
		cnt+=itr.second;

	cout << cnt << endl;


	return 0;
}

Measured memory_bytes: 16220
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll int64_t
#define all(v) v.begin(), v.end()
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)


int main() {

int N,K; cin >> N ;

vector<string> S(N);
rep(i,N) cin >> S[i];

int A=0,B=0,C=0,D=0;

rep(i,N){
  if(S[i]=="AC") {
    A++;
  } else if(S[i]=="WA"){
    B++;
  } else if(S[i]=="TLE"){
    C++;
  } else {
    D++;
  }
}


int ans = N%1000;
cout << "AC x " << A << endl;
cout << "WA x " << B << endl;
cout << "TLE x " << C << endl;
cout << "RE x " << D << endl;

return 0;
}

Measured memory_bytes: 6424
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>

int main()
{
	std::string s, t;
	std::vector<int> s_table[26], t_table[26];
	std::map<int, int> m;
	bool t_done[26]{};

	std::cin >> s >> t;
	for (unsigned int i = 0; i < s.length(); ++i)
		s_table[s[i] - 'a'].push_back(i);
	for (unsigned int i = 0; i < t.length(); ++i)
	{
		int tmp = t[i] - 'a';
		t_table[tmp].push_back(i);
		if (t_done[tmp]) continue;
		t_done[tmp] = true;
		m[i] = tmp;
	}

	for (int i = 0; i < 26; ++i)
	{
		if (!s_table[i].size()) continue;
		int tmp = s_table[i][0];
		if (m.find(tmp) == m.end() || t_table[m[tmp]] != s_table[i])
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");

	return 0;
}

Measured memory_bytes: 2824
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }





int N;
long long cost[1000], s[1000], b[1000];

int main() {
  while (cin >> N ) {
	for (int i = 0; i < N-1; ++i) cin >> cost[i] >> s[i] >> b[i];

	for (int i = 0; i < N; ++i) {
	  long long cur = 0;

	  for (int j = i; j < N-1; ++j) {
		int p = (cur + b[j] - 1) / b[j];
		long long syu = max(s[j], b[j] * p);
		cur = syu + cost[j];
	  }

	  cout << cur << endl;
	}
  }
}


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

#define endl '\n'

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(15);
}
const int MAXN = 1e5 + 100 ;
int A[MAXN] ; 
int dpinc[MAXN] ;
int dpdec[MAXN] ;
int dp[MAXN] ;
int main(int argc,char* argv[]) { 
    io() ;
    #ifndef ONLINE_JUDGE
  //      freopen("inp.txt", "r", stdin) ;
        // freopen("out.txt", "w", stdout);
    #endif
    int n ;
    cin >> n; 
    for(int i = 1;  i <= n ; i++){
        cin >> A[i] ;
    }
    dpinc[n] = dpdec[n] = n ;
    for(int i = n - 1 ; i >= 1 ; i--){
        if(A[i+1] < A[i]){
            dpinc[i] = i ;
        }
        else{
            dpinc[i] = dpinc[i+1] ;
        }
        if(A[i+1] > A[i]){
            dpdec[i] = i ;
        }
        else{
            dpdec[i] = dpdec[i+1] ;
        }
    }
    dp[n+1] = 0 ;
    dp[n] = 1 ;
    for(int i = n - 1; i >= 1 ; i--){
        dp[i] = min(dp[dpinc[i] + 1] + 1, dp[dpdec[i] + 1] + 1) ;
    }
    cout << dp[1] << endl ;
    return 0 ; 
}

Measured memory_bytes: 1792
#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>;

#define M 3e5

int main() {
  int N, K, i, j;
  cin >> N >> K;
  vector<int> v(M);
  vector<int> a(N);
  rep (i, N) {
    cin >> a.at(i);
    v.at(a.at(i)) ++;
  }
  sort(v.begin(), v.end(), greater<int>());

  i = 0;
  while (v.at(i) != 0){
    i++;
  }
  int id = i;
  int sum = 0;
  rep (i, K)
    sum += v.at(i);
  cout << N-sum << endl;
  return 0;
}


Measured memory_bytes: 2304
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int>A(N);
	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}
	int ans = 0;
	for (int i = 1; i < N; i++) {
		if (A.at(i) == A.at(i - 1)) {
			ans++;
			A.at(i) = 0;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vp = vector<pii>;
using vs = vector<string>;
using qi = queue<int>;
using qp = queue<pii>;
using pqi = priority_queue<int>;
using pqim = priority_queue<int, vector<int>, greater<int> >;
using ppp = pair<int, pair<int, int>>;
#define all(vec) vec.begin(), vec.end()
#define rall(vec) vec.rbegin(), vec.rend()
#define pb push_back
const ll mod = 998244353;
//const ll inf = 1e18;
const int inf = 1e9 + 7;
const int mxn = 2e5;

int n, q;
vi a;


void input() {

	cin >> n;
	a = vi(n);
	for (int& x : a) cin >> x;
	cin >> q;

}

void solve() {

	vl cnt(100001);
	for (int x : a) cnt[x]++;

	ll sum = 0;
	for (int i = 0; i <= 100000; ++i) {
		sum += cnt[i] * i;
	}

	while (q--) {
		ll b, c; cin >> b >> c;
		ll t = cnt[b];
		cnt[b] = 0;
		cnt[c] += t;
		sum -= t * b;
		sum += t * c;
		cout << sum << '\n';
	}


	return;
}

int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);

	input();
	solve();
}

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

//int _; 

int x;

int main()
{
	//for(scanf("%d",&_);_;_--)
	cin >> x;
	for(int i=0;i<1000;i++)
		for(int j=0;j<1000;j++)
		{
			for(int k=0;k<3;k++)
			{
				if(k == 1)
					i=-i;
				if(k == 2)
					j=-j;
				if(i*i*i*i*i-j*j*j*j*j == x)
				{
					cout << i << ' ' << j << endl;
					return 0;
				}
				i=abs(i);
				j=abs(j);
			}
		} 	
	return 0;
}

Measured memory_bytes: 3620
# D - Lamp
import numpy as np

h, w = map(int, input().split())

# 0: 障害物または壁 1: 通路
# 上下左右の壁の分を加味して+2したグリッドを用意する。
g = np.zeros((h+2,w+2),dtype=np.int64)
for i in range(h):
    grid = np.array(list(input()))
    g[i+1, 1:w+1] = (grid=='.')

# 横について考える
gW = np.copy(g)
gW = np.ravel(gW)
tWLeft = np.arange((w+2)*(h+2))
tWRight = np.copy(tWLeft)

tWLeft[gW==1] = 0
tWRight[gW[::-1]==1] = 0

np.maximum.accumulate(tWLeft, out=tWLeft)
np.maximum.accumulate(tWRight, out=tWRight)

tWRight = len(tWRight) - 1 - tWRight[::-1]

tW = tWRight-tWLeft-1
tW[gW==0] = 0
tW = tW.reshape(h+2, w+2)

# 縦について考える
gH = np.copy(g.T)
gH = np.ravel(gH)
tHLeft = np.arange((w+2)*(h+2))
tHRight = np.copy(tHLeft)

tHLeft[gH==1] = 0
tHRight[gH[::-1]==1] = 0

np.maximum.accumulate(tHLeft, out=tHLeft)
np.maximum.accumulate(tHRight, out=tHRight)

tHRight = len(tHRight) - 1 - tHRight[::-1]

tH = tHRight-tHLeft-1
tH[gH==0] = 0
tH = tH.reshape(w+2, h+2).T

#print(tW)
#print(tH)
print(np.max(tW+tH-1))


'''
# 横について考える
tblW = np.zeros((h, w),dtype=np.int64)
for i in range(h):
    for j in range(w):
        if grid[i, j]=='#' or tblW[i, j]>0:
            continue
        else:
            cnt = 1
            while j+cnt<w and grid[i, j+cnt]!='#':
                cnt += 1
            tblW[i, j:j+cnt] = cnt
print(tblW)
    
# 縦について考える
tblH = np.zeros((h, w),dtype=np.int64)
for j in range(w):
    for i in range(h):
        if grid[i, j]=='#' or tblH[i, j]>0:
            continue
        else:
            cnt = 1
            while i+cnt<h and grid[i+cnt, j]!='#':
                cnt += 1
            tblH[i:i+cnt, j] = cnt
print(tblH)

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, tblH[i, j]+tblW[i, j]-1)

print(ans)
'''

Measured memory_bytes: 356900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

int main() {
    ll k; cin >> k;
    vector<ll> v(k, 0);
    if (k % 2 == 0) {
        cout << "-1" << endl;
        return 0;
    }
    ll i = 0;
    ll rem = 0;
    ll prev_mod;
    ll prev_rem;
    while (true) {
        i++;
        ll cur_rem;
        if (i != 1) {
            cur_rem = prev_mod * 10;
            cur_rem %= k;
            if (cur_rem == 0 && rem != 0) {
                cout << "-1" << endl;
                return 0;
            }
        }
        else {
            cur_rem = 7 % k;
        }
        rem += cur_rem;
        rem %= k;
        if (rem == 0) break;
        prev_mod = cur_rem;
        prev_rem = cur_rem;
        if (v[rem] != 0) {
            cout << "-1" << endl;
            return 0;
        }
        v[rem]++;
    }
    cout << i << endl;
}

Measured memory_bytes: 11188
#include <bits/stdc++.h> 
using namespace std; 
int main(){
long long 	int n,sum=0;
	unordered_map<int,int> temp;
	cin>>n;
long long 	int a[2000005];
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum=sum+a[i];
		temp[a[i]]++;
	}
	int q;
	cin>>q;
	while(q--){
	long long 	int b,c;
		cin>>b>>c;
		if(temp.find((int)b)!=temp.end()){
			sum=sum-b*temp[b];
			sum=sum+c*temp[b];
			temp[c]=temp[c]+temp[b];
			temp[b]=0;
		}
		cout<<sum<<endl;
	}
	return 0;
}

Measured memory_bytes: 7552
from collections import deque
K = int(input())

q = deque()
q.append((1, 1, 1))
used = set()
while True:
    x, y, k = q.popleft()
    if k % K == 0:
        print(x)
        break
    if (x, 0, k*10%K) in used:
        continue
    else:
        used.add((x, 0, k*10%K))
    q.appendleft((x, 0, k*10%K))
    if (y + 1) % 10 == 0:
        q.appendleft((x, 0, k+1))
    else:
        q.append((x+1, y+1, k+1))


Measured memory_bytes: 143484
#!/usr/bin/env python3
import sys


def solve(S: int):
    s_array = list(str(S))
    N = len(s_array) - 1

    sum = 0
    for bit in range(2 ** N):
        num_string = s_array[0]
        for i in range(N):
            if bit & 1 << i:
                sum += int(num_string)
                num_string = s_array[i + 1]
            else:
                num_string += s_array[i + 1]
        sum += int(num_string)
    print(sum)
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <cmath>
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);

  ll a, b, h;
  cin >> a >> b >> h;
  ll ans = (a + b) * h / 2;

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <bitset>
#include<vector>
#include<utility>
#include<fstream>
#include<queue>
#include <iomanip>
#include<numeric>
#include<set>
#include<map>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i,n) for(int i=0;i<n;i++)
char ca;
const int MOD = 1000000007;
ll  c = 0, d = 0, e = 0, f = 0,g=0, n, i, j, k, h, w, o, a[100005], b[10000] = {};
queue<ll> q;
string s;
pair<ll, ll> p[20][20];
vector<vector<ll>> v;
const int MAX = 2005;
long long fac[MAX], finv[MAX], inv[MAX];

int main() {
	cin >> n;
	j = 0;
	rep(i, n) {
		cin >> f;
		if (j + 1 == f) {
			j++;
		}
	}

	if (j == 0)cout << -1;
	else cout << n-j;
	return 0;

}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;
const ll INF = (1LL << 62);

int main() {
  ll N, M;
  scanf("%lld %lld", &N, &M);

  vector<pair<ll, ll>> list(N);
  for (ll i = 0; i < N; i++) {
    ll a, b;
    scanf("%lld %lld", &a, &b);
    list[i] = make_pair(a, b);
  }
  sort(list.begin(), list.end());

  ll ans = 0;
  ll m = M;
  for (ll i = 0; i < N; i++) {
    ll price = list[i].first;
    ll num = list[i].second;

    ll n = min(m, num);
    ans += price * n;
    m -= n;
    if (m <= 0) {
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cstdio>

const int N=100005;
int ans[N];

int main(){
	int n,L,T,pos=0;
	scanf("%d%d%d\n",&n,&L,&T);
	for (int i=0,p=T/L,q=T%L;i<n;i++){
		int x,w;
		scanf("%d%d\n",&x,&w);
		if (w==2){
			w=-1;
			pos=(pos-p-(x<q))%n;
		}
		else pos=(pos+p+(x+q>L))%n;
		ans[i]=((x+w*T)%L+L)%L;
	}
	pos=(pos+n)%n;
	std::sort(ans,ans+n);
	for (int i=0;i<n;i++) printf("%d\n",ans[(i+pos)%n]);
}

Measured memory_bytes: 1536
def _level(n):
	if n == 0:
		return 1
	else:
		return 3 + 2 * level(n-1)

def _eat(n, x):
	if n == 0:
		return 1 if x > 0 else 0
	if x <= 1:
		return 0
	if x <= 1 + level(n-1):
		return eat(n-1, x-1)
	if x == 1 + level(n-1) + 1:
		return eat(n-1, level(n-1)) + 1
	if x <= 1 + level(n-1) + 1 + level(n-1):
		return eat(n-1, level(n-1)) + 1 + eat(n-1, x - (1 + level(n-1) + 1))
	else:
		return eat(n-1, level(n-1)) + 1 + eat(n-1, level(n-1))

store = {}

def level(n):
	if n not in store:
		store[n] = _level(n)
	return store[n]

def eat(n, x):
	if (n, x) not in store:
		store[(n, x)] = _eat(n, x)
	return store[(n, x)]


print(eat(*map(int, input().split())))


Measured memory_bytes: 38384
#include<iostream>
using namespace std;
int main() {
  int A,B;
  cin >> A >> B;
  if(A>=B+1){
  cout << 2*A-1 ;
  }
  else if(A==B){
  cout << 2*A;
  }
  else{
  cout << 2*B-1 ;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    int A, B;
    scanf("%d%d", &A, &B);
    if (A > 8 || B > 8) {
        printf("%s\n", ":(");
    } else {
        printf("%s\n", "Yay!");
    }
    return 0;
}

Measured memory_bytes: 128
x = raw_input()
x_list = x.split(" ")

x_list = map(int, x_list)

max = min = mid = 0
for i in range(1,3):
    if x_list[max] < x_list[i]:
        mid = max
        max = i
    elif x_list[min] > x_list[i]:
        mid = min
        min = i
    else:
        mid = i

print("%d %d %d" %(x_list[min], x_list[mid], x_list[max]))

Measured memory_bytes: 6396
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

struct Pair {
	int left, right;
};
int main() {
	int n; std::cin >> n;
	std::vector<int> permutation(n); for (auto& p : permutation) std::cin >> p;
	std::vector<Pair> section(n + 2);
	for (auto i = 0; i < section.size(); ++i) {
		section[i] = { i - 1, i + 1 };
	}
	section[0] = { 0, 1 };
	section[n + 1] = { n, n + 1};
	std::vector<int> indices(n + 1); 
	for (auto i = 0; i < permutation.size(); ++i) {
		indices[permutation[i]] = i + 1;
	}
	long long int result{ 0 };
	for (auto i = 1; i <= n; ++i) {
		auto idx = indices[i];
		auto sec = section[idx];
		auto left = sec.left;
		auto right = sec.right;
		result += i * (static_cast<long long int>(left - section[left].left) * (right - idx) + static_cast<long long int>(section[right].right - right) * (idx - left));
		section[left].right = right;
		section[right].left = left;
	}
	std::cout << result << std::endl;
}

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

int main(){
	int a, b;
	cin >> a >> b;
	int count = 0;
	if(b >= a) count++;
	cout << a-1+count << endl;
}

Measured memory_bytes: 256
x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
l=p[:x]+q[:y]
l.sort()
ans=sum(l)
for i in l:
    if r!=[]:
        if i<r[0]:
            ans+=r[0]-i
            del r[0]
        else:
            break
    else:
        break
print(ans)

Measured memory_bytes: 23200
#include<stdio.h>
#include<stdlib.h>
#define mymalloc(p,n) {p = malloc((n)*sizeof(*p));if ((p)==NULL) {printf("not enough memory?\n"); exit(1);};}

typedef struct{
	long key;
	long order;
	char suit;
}data;

data *readData(long n){
	long i,j;
	char c;
	data *A;
	mymalloc(A,n);
	for(i=0;i<n;i++){
		scanf(" %c %ld",&c,&j);
		A[i].key=j;
		A[i].order=i;
		A[i].suit=c;
	}
	return A;
}

void swap(data *i,data *j){
	data tmp;
	tmp=*i;
	*i=*j;
	*j=tmp;
}

long partition(data *A,long p,long r){
	long i,j,x;
	x=A[r].key;
	i=p;
	for(j=p;j<r;j++){
		if(A[j].key<=x){
			swap(&A[i],&A[j]);
			i++;
		}
	}
	swap(&A[i],&A[r]);
	return i;
}

void quickSort(data *A, long p, long r){
	long q;
	if(p<r){
		q=partition(A,p,r);
		quickSort(A,p,q-1);
		quickSort(A,q+1,r);
	}
}

int checkStab(data *A,long n){
	long i,k1,k2,o1,o2;
	k1=A[0].key;
	o1=A[0].order;
	for(i=1;i<n;i++){
		k2=A[i].key;
		o2=A[i].order;
		if(k1==k2&&o1>o2){
			return 1;
		}
		k1=k2;
		o1=o2;
	}
	return 0;
}
				

void printData(data *A,long n,int s){
	long i;
	if(s==0){
		printf("Stable\n");
	}
	if(s==1){
		printf("Not stable\n");
	}
	for(i=0;i<n;i++){
		printf("%c %ld\n",A[i].suit,A[i].key);
	}
}

main(){
	int s;
	long p,n;
	data *A;
	scanf("%ld",&n);
	A=readData(n);
	quickSort(A,0,n-1);
	s=checkStab(A,n);
	printData(A,n,s);
	free(A);
	return 0;
}

Measured memory_bytes: 2732
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define invrep(i,n) for(int i = (int)(n)-1; i >= 0; i--)
using ll = long long;

int main() {
    int x, n;
    cin >> x >> n;
    int tmp;
    if (n == 0) {
        // cin >> tmp;
        cout << x << endl;
        return 0;
    }

    vector<int> p(n);
    rep(i, n) cin >> p[i];
    sort(p.begin(), p.end());

    int min_tmp = 101;
    int near;
    invrep(i, n) {
        tmp = abs(x - p[i]);
        if (tmp < min_tmp) {
            min_tmp = tmp;
            near = p[i];
        }
    }

    int near_neg = near - 1;
    int near_pos = near + 1;
    invrep(i, n) {
        if (near_neg == p[i]) {
            near_neg = p[i] - 1;
        }
    }
    rep(i, n){
        if (near_pos == p[i]) {
            near_pos = p[i] + 1;
        }
    }

    if (abs(x - near_neg) <= abs(x - near_pos)) cout << near_neg << endl;
    else cout << near_pos << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;

int main() {

    int N;

    cin>>N;
    vector<int> h;
    vector<int> dp;
    h.resize(N);
    dp.resize(N+1);

    for(int i=0; i<N; ++i)
        cin>>h[i];

    dp[0] = 0;
    dp[1] = abs(h[1]-h[0]);

    for(int i=1; i<N-1; ++i)
    {
        int tmp1 = abs(h[i+1]-h[i]) + dp[i];
        int tmp2 = abs(h[i+1]-h[i-1])+dp[i-1];
        dp[i+1] = min(tmp1, tmp2);
    }

    cout<<dp[N-1]<<endl;



    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,x,d;
  cin>>n>>x>>d;
  if(d==0){
    if(x==0) cout<<1<<endl;
    else cout<<n+1<<endl;
    return 0;
  }
  if(d<0) d*=-1,x*=-1;

  using P = pair<Int, Int>;
  map<Int, vector<P> > mp;
  for(Int i=0;i<=n;i++){
    Int s=x*i;
    Int p=((s%d)+d)%d;
    Int l=i*(i-1)/2;
    Int r=i*(n-i+n-1)/2;
    // [l, r]
    mp[p].emplace_back((s-p)/d+l,(s-p)/d+r);
  }
  Int ans=0;
  const Int INF = 1e18;
  for(auto p:mp){
    auto vs=p.second;
    sort(vs.begin(),vs.end());
    Int lst=-INF;
    for(auto q:vs){
      Int l,r;
      tie(l,r)=q;
      //cout<<p.first<<":"<<l<<" "<<r<<endl;
      if(l<lst+1) l=lst+1;
      if(r-l+1>=0) ans+=r-l+1;
      lst=max(lst,r);
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
	int a[4],b[4];
	vector<int> r1,r2;
	while(scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3]) != EOF)
	{
		int map[10]={0};
		int hit=0,blow=0;
		scanf("%d %d %d %d",&b[0],&b[1],&b[2],&b[3]);
		for (int i=0; i<4; i++)
		{
			map[a[i]] = 1;
		}
		for (int i=0; i<4; i++)
		{
			if (a[i] == b[i])
			{
				hit++;
			} else if (map[b[i]]==1)
			{
				blow++;
			}
		}
		r1.push_back(hit);
		r2.push_back(blow);
	}
	for (int i=0; i<r1.size(); i++)
	{
		cout << r1[i] << " " << r2[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 0
S = gets.chomp.reverse!
W = ["dream".reverse, "dreamer".reverse, "erase".reverse, "eraser".reverse]
l = S.length
t = 0
while t < l
  for j in 0...4
    f = true
    for k in 0...W[j].length
      if S[t+k] != W[j][k]
        f = false
        break
      end
    end
    if f
      t += W[j].length
      break
    elsif j == 3
      t = l+1
      break
    end
  end
end
if t == l
  puts 'YES'
else
  puts 'NO'
end

Measured memory_bytes: 3964
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
const ll MOD=9998903;


ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

void solve() {
	ll i,j,count;
    ll N;
    cin>>N;
    vector<ll> A(N,0);
    vector<ll> exist(1001000,0);
	ll gcd=0;
	for(i=0;i<N;i++){
		cin>>A[i];
		gcd=GCD(gcd,A[i]);
		exist[A[i]]++;
	}
	for(i=2;i<=1000000;i++) {
		count=0;
		for(j=i;j<=1000000;j+=i) count+=exist[j];
		if(count>=2) break; //被りがあったら
	}
	if(i==1000001) {//被りがなければiは1000001となる
		cout<<"pairwise coprime"<<endl;
		return;
	}
	if(gcd==1) {
		cout<<"setwise coprime"<<endl;
	}
	else {
		cout<<"not coprime"<<endl;
	}
}


int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 18756
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int Dy[8] = {-1,-1,0,1,1,1,0,-1};
int Dx[8] = {0,1,1,1,0,-1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
int n;
string s;
char t[d5];
bool ok(char t[d5]){
    for(int i=1;i<n;i++){
        if((s[i]=='o'&&t[i]=='S')||(s[i]=='x'&&t[i]=='W')){
            t[i+1]=t[i-1];
        }
        else{
            if(t[i-1]=='S')t[i+1]='W';
            else t[i+1]='S';
        }
    }

    if(t[0]!=t[n])return false;
    if((s[0]=='o'&&t[0]=='S')||(s[0]=='x'&&t[0]=='W')){
        if(t[1]==t[n-1])return true;
        else return false;
    }
    else{
        if(t[1]!=t[n-1])return true;
        else return false;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);    
    cin>>n>>s;
    t[0]='S';t[1]='S';
    if(ok(t)){
        for(int i=0;i<n;i++)cout<<t[i];
        cout<<endl;
        return 0;
    }
    t[0]='S';t[1]='W';
    if(ok(t)){
        for(int i=0;i<n;i++)cout<<t[i];
        cout<<endl;
        return 0;
    }
    t[0]='W';t[1]='S';
    if(ok(t)){
        for(int i=0;i<n;i++)cout<<t[i];
        cout<<endl;
        return 0;
    }
    t[0]='W';t[1]='W';
    if(ok(t)){
        for(int i=0;i<n;i++)cout<<t[i];
        cout<<endl;
        return 0;
    }
    cout<<-1<<endl;
}


Measured memory_bytes: 720
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
tA=list(reversed(A))
l=[0]
r=[0]
m=[]
for i in range(N):
  l.append(gcd(l[i],A[i]))
  r.append(gcd(r[i],tA[i]))
r=list(reversed(r))
for i in range(N):
  m.append(gcd(l[i],r[i+1]))
print(max(m))

Measured memory_bytes: 16116
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<class T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<class T,class Size=typename vector<T>::size_type>inline auto vector_2d(Size h,Size w,T v){return vector<vector<T>>(h,vector<T>(w,v));}
template<class RandomAccessIterator,class Pair=typename iterator_traits<RandomAccessIterator>::value_type>inline void sort_pairs_by_second(RandomAccessIterator first,RandomAccessIterator last){sort(first,last,[](const Pair&p1,const Pair&p2){return p1.second<p2.second||(p1.second==p2.second&&p1.first<p2.first);});}

int main()
{
    string s;cin>>s;
    auto c=count(s.begin(),s.end(),'R');
    if(c==0||c==1||c==3){
        cout<<c<<endl;
    }else{
        cout<<(s=="RSR"?1:2)<<endl;
    }
}


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

using namespace std;

int main() {
  int n; cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  int cur_max = h[0];
  for (int i = 1; i < n; i++) {
    if (cur_max - h[i] > 1) {
      cout << "No" << endl;
      return 0;
    }
    cur_max = max(cur_max, h[i]);
  }
  cout << "Yes" << endl;
  return 0;
}

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

#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define FORW(a, b, c) for(int a = b; a >= c; --a)
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define int long long




typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 2e5 + 100;
const int mod = 998244353;
const int Maxn = 1e5;
const int oo = 1e18;
const double PI = ((double)2.00 * (double)asin(1));

int n, cnt;
int a[N], ans[N];
vector<int> vi[N];
vector<int> tmp;

void solve(int u, int pu) {
	ii cur = {-1, -1};

	if(!cnt || tmp.back() < a[u]) {
		tmp.pb(a[u]);
		cnt += 1;
	} else {
		int pos = lower_bound(tmp.begin(), tmp.end(), a[u]) - tmp.begin();
		cur = {pos, tmp[pos]};
		tmp[pos] = a[u];
	}
	ans[u] = cnt;
	for(auto v: vi[u]) if(v != pu) {
		solve(v, u);
	}

	if(cur.fi == -1) {
		tmp.pop_back();
		cnt -= 1;
	} else {
		tmp[cur.fi] = cur.se;
	}
}

signed main() {
	#ifdef TEST
	freopen("test.inp", "r", stdin);
	//freopen("athletic.in", "r", stdin);
	//freopen("athletic.out", "w", stdout);
	#endif //TEST

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
	FOR(i, 1, n - 1) {
		int u, v; cin >> u >> v;
		vi[u].pb(v); vi[v].pb(u);
	}

	solve(1, 1);
	FOR(i, 1, n) cout << ans[i] << '\n';
}


Measured memory_bytes: 29072
using System;
using System.Collections.Generic;
using System.IO.Pipes;
using System.Linq;
using System.Text;

namespace cswork
{
    class Program
    {
        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);
                i = 0;
                return next();
            }

            public int nextInt()
            {
                return int.Parse(next());
            }

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

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

        public Program() { }

        static void Main(string[] args)
        {
            new Program().Omame();
        }

        Scanner cin;
        const int MAXIN = 1024;
        bool[] used = new bool[MAXIN];
        int[] perm = new int[MAXIN];

        List<int[]> permList = new List<int[]>();

        public void Permutation(int pos, int n, int length)
        {
            if (pos == n)
            {
                permList.Add((int[])perm.Clone());
            }

            for (int i = 0; i < n; i++)
            {
                if (!used[i])
                {
                    perm[pos] = i;
                    used[i] = true;
                    Permutation(pos + 1, n, length);
                    used[i] = false;
                }
            }
        }

        void Omame()
        {
            cin = new Scanner();
            string S = cin.next();

            if (!isKaibun(S))
            {
                Console.WriteLine("No");
                return;
            }

            if (!isKaibun(S.Substring(0, (S.Length - 1) / 2)))
            {
                Console.WriteLine("No");
                return;
            }

            if (!isKaibun(S.Substring((S.Length + 3) / 2 - 1)))
            {
                Console.WriteLine("No");
                return;
            }

                Console.WriteLine("Yes");
        }

        bool isKaibun(string s)
        {
            for (int i = 0; i < s.Length / 2; i++)
            {
                if (s[i] != s[s.Length - 1 - i])
                {
                    return false;
                }
            }
            return true;
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <bitset>
#include <chrono>
#include <climits>

using namespace std;

#define pb push_back
#define x  first
#define y  second
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
// #define debug(...) 42
#endif

const int MX =2e5;
const ll MD= LLONG_MAX;
const ld PI=acos(-1);

int main() {
	fast_cin();
	int t=1;
	// cin>>t;
	while(t--)
	{
		ll ans=0;
		map<int,int>mp;
		int n,a[MX];
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
			ans+=mp[a[i]-i];
			mp[-a[i]-i]++;
		}
		cout<<ans<<"\n";
	}
	return 0;	
}


Measured memory_bytes: 21456
N = int(input())
xy = []
for i in range(N):
    A = int(input())
    xy.append([])
    for j in range(A):
        xy[i].append(tuple(map(int, input().split())))
 
ans = 0
 
for i in range(2 ** N):
    h = [0] * N
 
    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
    
    flag = False
    for i in range(N):
        if h[i] == 1:
            for x, y in xy[i]:
                if h[x-1] != y:
                    flag = True
                    break
            if flag:
                break
    
    if not flag:
        ans = max(ans, sum(h))
 
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> void cmax(T& a, U b) { if (a<b) a = b; }
template<class T, class U> void cmin(T& a, U b) { if (a>b) a = b; }

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

  ll n;
  vector<ll> a(5);
  cin >> n;
  rep(i, 5) cin >> a[i];
  sort(all(a));

  if (a[0] == 1) {
    cout << 4+ n << endl;
    return 0;
  }
  cout << 5 + n/a[0] << endl;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define INF INT_MAX/3
#define MAX_V 200

int V;
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

bool dfs(int v) {
    used[v] = true;
    rep(i, G[v].size()) {
        int u = G[v][i], w = match[u];
        if(w < 0 || (!used[w] && dfs(w))){
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int bipartite_matching() {
    int res = 0;
    memset(match, -1, sizeof(match));
    rep(v, V) if(match[v] < 0) {
        memset(used, 0, sizeof(used));
        if(dfs(v)) res++;
    }
    return res;
}

int main() {
    cin.sync_with_stdio(false);
    cin >> V;
    P red[V], blue[V];
    rep(i, V) cin >> red[i].fi >> red[i].se;
    rep(i, V) cin >> blue[i].fi >> blue[i].se;
    rep(i, V) rep(j, V) {
        if (red[i].fi < blue[j].fi && red[i].se < blue[j].se) add_edge(i, j + V);
    }

    cout << bipartite_matching() << endl;
    return 0;
}

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

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

    int cnt = 0;
    bool flag = 1;
    while(flag){
        flag = 0;
        for(int j = n-1; j > 0; j--){
            if(a[j] < a[j-1]){
                swap(a[j], a[j-1]);
                flag = 1;
                cnt++;
            }
        }
    }
    for(int k = 0; k < n; k++)
        cout << a[k] << (k == n-1 ? '\n' : ' ');
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3112
import java.util.ArrayList;
import java.util.Scanner;
import java.util.function.Function;

/**
 * Created by btk on 2017/10/13.
 */
public class Main {
   public static void main(String[] args){
       Scanner sc=new Scanner(System.in);
       int R=sc.nextInt();
       int C=sc.nextInt();
       String[] in = new String[R+2];
       in[0]="...............................................................................................";
       in[R+1]="...............................................................................................";
       for (int i = 1; i <= R; i++) {
           in[i] = "." + sc.next() + ".";
       }
       for (int i = 1; i <= R; i++) {
           for (int j = 1; j <= C; j++) {
               if(in[i].charAt(j)=='#')System.out.print('#');
               else{
                   int cnt=0;
                   int[] dr={0,0,1,-1,-1,-1,1,1};
                   int[] dc={1,-1,0,0,-1,1,-1,1};
                   for (int k = 0; k < 8; k++) {
                       cnt+=(in[i+dr[k]].charAt(j+dc[k])=='#')?1:0;
                   }
                   System.out.print(cnt);
               }
           }
           System.out.println();
       }

       sc.close();
   }
}


Measured memory_bytes: 23764
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

N,C = li()
MAX = 10**5

stc = []
for _ in range(N):
    stc.append(list(li()))
    
rec = [[0 for _ in range(MAX+1)] for _ in range(C)]
for s,t,c in stc:
    rec[c-1][s-1] += 1
    rec[c-1][t] -= 1
    
for i in range(C):
    rec[i] = list(accumulate(rec[i]))
    rec[i] = [min(1,reci) for reci in rec[i]]
    
rec_total = rec[0]
    
for i in range(1,C):
    for j in range(MAX+1):
        rec_total[j] = rec_total[j] + rec[i][j]

print(max(rec_total))

Measured memory_bytes: 51884
#include <iostream>


using namespace std;


struct obstacles {
  bool above; // true if obstacle above
  bool left; // true if obstacle to the left
  int value; // no. of ways to get to this box
};



int main() {

  int input;
  cin >> input;

  for (int j = 0; j < input; j++) {
    int goalx, goaly;
    cin >> goalx >> goaly;
    
    obstacles grid[goalx + 1][goaly + 1]; // create grid

    //initialize grid
    for (int xi = 0; xi <= goalx; xi++) { // xi increases to the right
      for (int yi = 0; yi <= goaly; yi ++) { // yi increase downwards
	if (yi == 0) { 
	  grid[xi][yi].above = true; // top boundary
	} else {
	  grid[xi][yi].above = false;
	}
	if (xi == 0) {
	  grid[xi][yi].left =  true; // left boundary
	} else {
	  grid[xi][yi].left = false;
	}
	grid[xi][yi].value = 0;
      }
    }

    
    int n_matatabi; // number of matatabis
    
    cin >> n_matatabi;
    
     for (int m = 0; m < n_matatabi; m++) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;

      //initialize obstacles for matatabis
      if (x1 == x2) { // vertical link |
	if (y1 > y2) {
	  grid[x1][y1].above = true;
	} else {
	  grid[x1][y2].above = true;
	} 
      }
      if (y1 == y2) { //horizontal link -
	if (x1 > x2) {
	  grid[x1][y1].left = true;
	} else {
	  grid[x2][y1].left = true;
	}
      }
      }

  
    //dynamic programming
    for (int x = 0; x <= goalx; ++x) {
      for (int y = 0; y <= goaly; ++y) {
	if (x == 0 && y == 0) {
	  grid[0][0].value = 1;
	  continue;
	}
	int above = 0, left = 0;
	if (grid[x][y].above == false) {
	  above = grid[x][y-1].value;
	}
	if (grid[x][y].left == false) {
	  left = grid[x - 1][y].value;
	}
	grid[x][y].value = above + left;
      }
    }
    /*
    //function for printing
    for (int rowtest = 0; rowtest <= goalx; ++rowtest) {
      for (int coltest = 0; coltest <= goaly; ++coltest) {
	cout << grid[rowtest][coltest].value << " ";
      }
      cout << endl;
    }
    */
    
     
    if (grid[goalx][goaly].value == 0) { 
      cout << "Miserable Hokusai!" << endl; // if no path
    } else {
      cout << grid[goalx][goaly].value << endl;
    }
  }
}
  
 


  
  
  
 

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	string s, t, u;
	cin >> s >> t;
	for (int i = 0; i < 2 * n; i++)
		cout << ((i % 2 == 0) ? s[i / 2] : t[(i - 1) / 2]);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 2e+9 + 10;
typedef pair<ll, ll> P;

const int MAX_N = (3e+6)+10;
vec nCm(MAX_N+1,0);
vec fact(MAX_N+1,0),fact_inv(MAX_N+1,0);

ll fastpow(ll a, ll pw) {
    ll res = 1;
    while (pw) {
        if (pw & 1) res = res * a % MOD;
        a = a * a % MOD;
        pw >>= 1;
    }
    return res;
}
void makefact(ll n){//MODは素数かつnより大きい
    ll ans = 1;
    fact.at(0) = ans;
    fact_inv.at(0) = ans;
    reps(i,1,n+1){
        (ans *= i)%=MOD;
        fact.at(i) = ans;
        fact_inv.at(i) = fastpow(ans,MOD-2);
    }
    return;
}
void makenCm(ll n){
    rep(i,n+1){
        ll ans = fact.at(n);
        (((ans*=fact_inv.at(n-i))%=MOD)*=fact_inv.at(i))%=MOD;
        nCm.at(i) = ans;
    }
    return;
}

ll f(ll a, ll b){
    ll res = fact[a + b + 2];
    (res *= fact_inv[b + 1])%=MOD;
    (res *= fact_inv[a + 1])%=MOD;
    (res += MOD - 1)%=MOD;
    return res;
}


int main() {
    makefact(3e+6);
    ll a, b;
    cin>>a>>b>>A>>B;
    --a;
    --b;
    cout<<(MOD * 2 + f(A, B) - f(A, b) - f(a, B) + f(a, b))%MOD<<endl;
}

Measured memory_bytes: 70528
K, N = map(int, input().split())
A = list(map(int, input().split()))
a = 0
ans = 0
for i in range(N-1):
    a = max(a,A[i+1]-A[i])
    ans += A[i+1]-A[i]

if A[0]+K-A[-1]>=a:
    print(ans)
else:
    print(ans+A[0]+K-A[-1]-a)


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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
  cout.precision(17);

  int n;cin>>n;
  double res=0;
  for(int i=0;i<n;i++){
    double v;cin>>v;
    res += (1.0 / v);
  }
  cout<<1.0/res<<endl;

  return 0;
}


Measured memory_bytes: 256