akhauriyash/Code-Regression huggingface dataset:
#pragma gcc optimize("Ofast")

#include "bits/stdc++.h"
using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
inline void output(int _x) {
    char _buff[20]; int _f = 0;
    if(_x == 0)putchar('0');
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
    return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
     return _out(s,c.begin(),c.end());
 }
#ifdef erd1
    #define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
    #define pprint(x)
#endif
// code starts here
vector<long double> tail, odds;
vector<vector<int>> G1, G2;
signed main(){
    int n, m;
    cin >> n >> m;
    tail.resize(n+1); odds.resize(n+1); G1.resize(n+1); G2.resize(n+1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        G1[a].pb(b);
        G2[b].pb(a);
    }
    odds[1] = 1;
    for(int i = 2; i <= n; i++)
        for(auto x: G2[i])
            odds[i]+=odds[x]/G1[x].size();
    for(int i = n-1; i >= 1; i--){
        for(auto x: G1[i])
            tail[i] += tail[x]+1;
        if(G1[i].size())tail[i]/=G1[i].size();
    }
    long double loss = 0;
    //cout << tail << endl << odds << endl;
    for(int i = 1; i <= n; i++){
        if(G1[i].size() > 1)
            for(auto x: G1[i])
                loss = max(loss, odds[i]*tail[i]-odds[i]*(tail[i]*G1[i].size()-1-tail[x])/(G1[i].size()-1));
    }
    cout << setprecision(20) << fixed << tail[1]-loss << endl;
}


Measured memory_bytes: 2560
#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 n,m,q; //dfsを外で作るのでグローバル変数で
vector<int> a,b,c,d;
int ans;

void dfs(vector<int> A){
  if(A.size() == n+1){ //終了条件
    int now = 0;
    rep(i,q){
      if(A[b[i]] - A[a[i]] == c[i]) now += d[i];
    }
    ans = max(ans, now);
    return;
  }

  A.push_back(A.back()); //Aに直前の数字を入れる。次につなげる 
  while(A.back() <= m){
    dfs(A);
    A.back()++;
  }
}

int main() {
  cin >> n >> m >> q;
  a = b = c = d = vector<int>(q);
  rep(i,q){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  dfs(vector<int>(1,1));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;


class Program
{
    public static long Read()
    {
        return long.Parse(Console.ReadLine());
    }

    public static long[] Reads()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }


    public static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);

        var input = Reads();
        var a = input[0];
        var b = input[1];
        var k = input[2];
        if (a < b)
        {
            long tmp = b;
            b = a;
            a = tmp;
        }
        var x = new List<long>();
        for(long i = b; i >= 1; i--)
        {
            if (a % i == 0 && b % i == 0)
            {
                x.Add(i);
            }
        }
        Console.WriteLine(x[(int)k - 1]);



        Console.Out.Flush();
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
/*
R=0
G=1
B=2
*/

int main(){
    int n;
    string ss;
    cin>>n>>ss;
    long long ans = 0;
    int f[4002][3]={0};
    for(int i=ss.length()-1;i>=0;i--){
        if(ss[i]=='R'){
            f[i][0]=f[i+1][0]+1;
            f[i][1]=f[i+1][1];
            f[i][2]=f[i+1][2];
        }
        else if(ss[i]=='G'){
            f[i][1]=f[i+1][1]+1;
            f[i][0]=f[i+1][0];
            f[i][2]=f[i+1][2];
        }
        else {
            f[i][2]=f[i+1][2]+1;
            f[i][0]=f[i+1][0];
            f[i][1]=f[i+1][1];
        }
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(ss[i]=='R' && ss[j]=='G'){
                ans += f[j][2];
                if(ss[2*j-i]=='B')
                    ans=ans-1;
            }
            else if(ss[i]=='R' && ss[j]=='B'){
                ans += f[j][1];
                if(ss[2*j-i]=='G')
                    ans=ans-1;
            }
            else if(ss[i]=='B' && ss[j]=='G'){
                ans += f[j][0];
                if(ss[2*j-i]=='R')
                    ans=ans-1;
            }
            else if(ss[i]=='B' && ss[j]=='R'){
                ans += f[j][1];
                if(ss[2*j-i]=='G')
                    ans=ans-1;
            }
            else if(ss[i]=='G' && ss[j]=='R'){
                ans += f[j][2];
                if(ss[2*j-i]=='B')
                    ans=ans-1;
            }
            else if(ss[i]=='G' && ss[j]=='B'){
                ans += f[j][0];
                if(ss[2*j-i]=='R')
                    ans=ans-1;
            }

        }
    }
    cout<<ans<<endl;
    /*
    for(int i=0;i<n;i++){
            cout<<ss[i]<<" ";
        for(int j=0;j<3;j++){
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/21  Problem: ABC 061 A / Link: http://abc061.contest.atcoder.jp/tasks/abc061_a  ----- */


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

	LL A, B, C; cin >> A >> B >> C;
	LL ans = (A<=C && C<=B);
	
	
	cout << (ans?"Yes":"No") << "\n";

	return 0;
}


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

using namespace std;

namespace Solver {

    int L, a0;
    inline bool Read() {
        cin >> a0 >> L;
        if (a0 == 0 && L == 0) return false;
        return true;
    }

    inline void Work() {
        vector<int> a;
        a.push_back(a0);
        for (int i = 1;; i++) {
            vector<int> vi(L, 0);
            for (int k = 0, a_ = a[i - 1]; k < L || a_ > 0; k++) {
                vi[k] = a_ % 10;
                a_ /= 10;
            }

            sort(vi.begin(), vi.end());
            int s = 0, l = 0;
            for (int k = 0; k < L; k++) {
                s = s * 10 + vi[k];
                l = l * 10 + vi[L - k - 1];
            }

            a.push_back(l - s);
            bool fin = false;
            for (int j = 0; j < i; j++) {
                if (a[i] == a[j]) {
                    cout << j << " " << a[i] << " " << i - j << endl;
                    fin = true;
                    break;
                }
            }

            if (fin) break;
        }
    }

    inline void Solve() {
        while (Read()) Work();
    }
}

int main() {
    Solver::Solve();
}

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

int main(){
	long long int n;
  	cin>>n;
  	long long int fhund = 0, five = 0;
  	fhund = n/500;
  	long long int rem = n%500;
  	five = rem/5;
  	cout<<fhund * 1000 + five*5;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <deque>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <bitset>

#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define FILL(x, y) memset(x, y, sizeof(x))
#define pb push_back
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

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 (a > b) {
      a = b;
      return 1;
   }
   return 0;
}

using namespace std;
using ll = long long;

const int kInf = 1e9;
const ll kLInf = 1e18;

int gcd (int a, int b) {
   return b ? gcd(b, a % b) : a;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int N;
int a[3010];
ll dp[3010][3010];
bool flg[3010][3010];

ll REC(int l, int r);

int main()
{
   cin >> N;
   REP(i, N) {
      cin >> a[i];
   }
   cout << REC(0, N-1) << endl;
   return 0;
}

ll REC(int l, int r)
{
   if (flg[l][r]) return dp[l][r];
   flg[l][r] = 1;
   if (l==r) {
      eprintf("dp[%d][%d] = %d\n", l, r, a[l]);
      return dp[l][r] = a[l];
   }
   ll left = a[l] - REC(l+1, r);
   ll right = a[r] - REC(l, r-1);
   eprintf("dp[%d][%d] = %d\n", l, r, max(left, right));
   return dp[l][r] = max(left, right);
}
   


Measured memory_bytes: 78592
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
typedef long long ll;
const int MAX_H=2e5,MAX_W=2e5,MAX_N=2e5;
int H,W,N;
set<int> blk[MAX_W];
int main(){
	cin>>H>>W>>N;
	REP(i,N){
		int x,y;
		cin>>x>>y;
		x--;
		y--;
		blk[y].insert(x);
	}
	REP(i,W){
		blk[i].insert(H);
	}
	int ans=H;
	int x,y;
	x=y=0;
	do{
		auto ite=blk[y].upper_bound(x);
		ans=min(ans,*ite);
		if (y==W-1){
			break;
		}
		if (blk[y].find(x+1)!=blk[y].end() || x==H-1){
			break;
		}
		x++;
		if (blk[y+1].find(x)==blk[y+1].end()){
			y++;
		}
	}while(1);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 28416
#include <iostream>

using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a <= b && b <= c)
        cout << a << " " << b << " " << c << endl;
    else if (a <= c && c <= b)
        cout << a << " " << c << " " << b << endl;
    else if (c <= a && a <= b)
        cout << b << " " << a <<" " << c << endl;
    else if (c <= b && b <= a)
        cout << c << " " << b << " " << a << endl;
    else if (b <= c && c <= a)
        cout << b << " " << c << " " << a << endl;
    else if (c <= a && a <= b)
        cout << c << " " << a << " " << b << endl;
    
 

}




Measured memory_bytes: 3092
using System;
using System.Collections.Generic;
using System.Numerics;
using System.Linq;
using static System.Math;

class MainClass
{

    public static void Main(string[] args)
    {
        var N = LnInt();
        var Vs = new int[N][];
        for (int i = 0; i < Vs.Length; i++) { Vs[i] = LnInts(); }
        var dp = new int[N + 1][];
        for (int i = 0; i < dp.Length; i++) { dp[i] = new int[3]; }

        for (int i = 0; i < N; i++)
        {
            dp[i + 1][0] = Max(dp[i][1] + Vs[i][0], dp[i][2] + Vs[i][0]);
            dp[i + 1][1] = Max(dp[i][2] + Vs[i][1], dp[i][0] + Vs[i][1]);
            dp[i + 1][2] = Max(dp[i][0] + Vs[i][2], dp[i][1] + Vs[i][2]);
        }
        var result = Max(dp[N][0], Max(dp[N][1], dp[N][2]));
        Console.WriteLine(result);
    }

    public static long Gcd(long a, long b) { if (a > b) { var r = a % b; if (r == 0) return b; else return Gcd(b, r); } else { var r = b % a; if (r == 0) return a; else return Gcd(a, r); } }
    public static int Gcd(int a, int b) { if (a > b) { var r = a % b; if (r == 0) return b; else return Gcd(b, r); } else { var r = b % a; if (r == 0) return a; else return Gcd(a, r); } }
    public static int[] LnInts() { var vs = Console.ReadLine().Trim().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); var ins = new int[vs.Length]; for (int i = 0; i < vs.Length; i++) ins[i] = int.Parse(vs[i]); return ins; }
    public static int LnInt() { var vs = Console.ReadLine().Trim(); return int.Parse(vs); }
    public static long[] LnLngs() { var vs = Console.ReadLine().Trim().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); var ins = new long[vs.Length]; for (int i = 0; i < vs.Length; i++) ins[i] = long.Parse(vs[i]); return ins; }
    public static long LnLng() { var vs = Console.ReadLine().Trim(); return long.Parse(vs); }
    public static string[] LnStrs() { var vs = Console.ReadLine().Trim().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); return vs; }
    public static string LnStr() { var vs = Console.ReadLine().Trim(); return vs; }
}

Measured memory_bytes: 26556
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long mod = 1000000007;

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

	int n;
	cin >> n;
	string s,t;
	cin >> s >> t;

	for (int i = 0; i < n; ++i) {
		cout << s[i] << t[i];
	}

	cout << "\n";

	return 0;
}


Measured memory_bytes: 256
N = int(input())

if N in (1, 2):
    print(N)
    exit()

for i in range(2, 10 ** 4):
    x = i * (i + 1) / 2
    if x - (i - 1) <= N <= x:
        a = i
        break

ans = [i for i in range(1, a + 1)]
b = a*(a+1)/2 - N

for i in range(1, a+1):
    if i != b:
        print(i)



Measured memory_bytes: 9308
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std; 
#define MAXN 50
#define MAXM 50
int main(int argc,char const* argv[])
{
  int n,m,a,b,i;
  cin >> n >> m;
  vector<int> road(MAXN,0);
  for(i=0;i<n;i++)
    {
      road[i]=0;
    }
  for(i=0;i<m;i++)
    {
      cin >> a >> b;
      road[a-1]++;
      road[b-1]++;
    }
  for(i=0;i<n;i++)
    {
      printf("%d\n",road[i]);
    }
  return 0;
}

Measured memory_bytes: 256
import string
import re
import datetime
import calendar
import collections
import heapq
import bisect
import array

import numpy as np
import scipy as sp

n, m = map(int, input().split())

graph = collections.defaultdict(list)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

used = set()
s = 1
t = graph[1][0]
used.add(s)
used.add(t)
path_s = [s]
path_t = [t]

while True:
    for next in graph[s]:
        if not next in used:
            used.add(next)
            s = next
            path_s.append(s)
            break
    else:
        break

while True:
    for next in graph[t]:
        if not next in used:
            used.add(next)
            t = next
            path_t.append(t)
            break
    else:
        break

print(len(path_s)+len(path_t))

for x in path_s[::-1]:
    print(x,end=" ")
for x in path_t[:len(path_t)-1]:
    print(x,end=" ")
print(path_t[len(path_t)-1])


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

int main(void){
    int a,b,c,d,e;
    scanf("%d%d",&a,&b);
    c = a + b;
    d = a-b;
    e = a*b;
    if(c>=d && c>=e){
        printf("%d",c);
    }else if(d>=c && d>=e){
        printf("%d",d);
    }else if(e >=c && e>=d){
        printf("%d",e);
    }
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
main() 
{
  int a,b;
  scanf("%d%d",&a,&b);
 
  if( a > b)
    printf("a > b\n");

  else if( a < b)
    printf("a < b\n");

  else
    printf("a == b\n");

  return 0;
}

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

int main(void){
    int a[5];
    int tmp;
    for(int i=0;i<5;i++){
        cin>>tmp;
        a[i]=tmp*(-1);
    }
    sort(a,a+5);
    for(int i=0;i<5;i++){
        cout<<-1*a[i];
        if(i<4){
            cout<<" ";
        }
        else{
            cout<<endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3144
n,m=map(int,input().split())
ll=0
rr=n+1
for i in range(m):
    l,r=map(int,input().split())
    ll=max(ll,l)
    rr=min(rr,r)

if rr<ll:
    print(0)
else:
    print(rr-ll+1)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;




int main()
{
    ll N;
    cin >> N;
    ll ans = 0;
    for (ll i = 1; i*i <= N; i++) {
        if(N%i==0){
            ans = N/i;
        }
    }
    string a = to_string(ans);
    cout << a.length() << endl;
    
    return 0;
}



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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF 100000000
ll n,cap,w[105],v[105];
ll dp[102][100005];
ll f(ll i, ll cap){

    if(i>=n || cap<=0) return 0;

    if(dp[i][cap]!=-1) return dp[i][cap];

    ll ret1=0,ret2=0;

    if(cap>=w[i]) ret1 = v[i]+f(i+1,cap-w[i]);
    ret2 = f(i+1,cap);


    return dp[i][cap] = max(ret1,ret2);




}


int main(){

    cin>>n>>cap;
    for(ll i=0;i<n;i++) cin>>w[i]>>v[i];
    memset(dp,-1,sizeof(dp));
    cout<<f(0,cap);
    return 0;
}

Measured memory_bytes: 80000
INF = 1000000

until (n = gets.to_i).zero?
  edge = Array.new
  degree = Array.new(n){0}
  (n - 1).times do
    from, to, weight = gets.split.map(&:to_i)
    from -= 1
    to -= 1
    edge << [from, to, weight]
    degree[from] += 1
    degree[to] += 1
  end

  (1...n).each do |i|
    next unless degree[i] == 1
    edge.reject! do |(from, to, weight)| from == i || to == i end
  end

  answer = edge.empty? ? 0 : edge.map{|e| e.last}.inject(&:+) * 2

  cost = Array.new(n){Array.new(n){INF}}
  edge.each do |(from, to, weight)| cost[from][to] = cost[to][from] = weight end
  n.times do |i| cost[i][i] = 0 end
  n.times do |k|
    n.times do |i|
      n.times do |j|
        cost[i][j] = [cost[i][j], cost[i][k] + cost[k][j]].min
      end
    end
  end
  answer -= cost[0].select{|v| v != INF}.max

  p answer
end

Measured memory_bytes: 6128
N = int(input())
X = [None]*N
a = 0
for i in range(N):
    A, B = map(int, input().split())
    X[i] = (A+B, A, B)
X.sort(reverse=1)
ans = 0
for i in range(N):
    if i % 2 == 0:
        ans += X[i][1]
    else:
        ans -= X[i][2]
print(ans)

Measured memory_bytes: 55896
#include <stdio.h>
#include <math.h>
 
using namespace std;
 
int main(){
    double x1,y1,x2,y2;
    scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
    printf("%.8lf\n",sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}


Measured memory_bytes: 2684
import math

def distance(a, b, c, d):
    return math.sqrt(((a - b) ** 2) + ((c - d) ** 2))

N = int(input())

xy = []
for i in range(N):
    tmp = list(map(int, input().split()))
    xy.append(tmp)
    
sum_dis = 0
dis_list = []
for i in range(N-1):
    for j in range(i+1, N):
        dis_list.append(distance(xy[i][0], xy[j][0], xy[i][1], xy[j][1]))


print(sum(dis_list) * (math.factorial(N-1)*2) / (math.factorial(N)))

Measured memory_bytes: 3064
N = gets.to_i
height_list = gets.split(' ').take(N).map(&:to_i)

MAX_VALUE = (10 ** 4) * (10 ** 5) + 1
dp = Array.new(N) { MAX_VALUE }
dp[0] = 0

(0...(N - 1)).each do |i|
  height = height_list[i]
  dp[i + 1] = [
    dp[i + 1],
    dp[i] + (height - height_list[i + 1]).abs
  ].min
  next if i == (N - 1) - 1
  dp[i + 2] = [
    dp[i + 2],
    dp[i] + (height - height_list[i + 2]).abs
  ].min
end

puts dp[N - 1]


Measured memory_bytes: 11660
A = int(input())
B = int(input())
C = int(input())
X = int(input())
 
count = 0
 
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if (i*500+j*100+k*50) == X:
                count += 1
print(count)

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int x;
	cin >> x;
	if (x == 3 || x == 5 || x == 7)cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch FrogJump | diff FrogJump.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address FrogJump.cpp && ./a.out

/*
 
 5/26/2019
 
 17:00-18:00 give up
 20:50- read editorial
 
 http://kmjp.hatenablog.jp/entry/2019/05/26/1330
 https://img.atcoder.jp/abc128/editorial.pdf
 
 I thought there are two cases
 1. k*A-k*B=N-1
 2. (k+1)*A-k*B=N-1
 
 However case #1 cannot happen. If happened, step is beyond N-1 😡
 
 There are two points
 
 1. Transform formula to upper-bound by multiple of two variables
 
 (k+1)*A+k*B=N-1
 
 2. Recurrence relation for # of steps
 
 
 
 */

const int MAX_N=1e6+1;
LL S[MAX_N];
int N;

void solve() {
  LL res=0;
  FOR(c,1,N-1) {
    LL cur=0;
    SETI viz;
    FOR(k,1,(N-1)/c) {
      LL a=k*c,b=N-1-k*c;
      if(b<=0||a>=N-1) break;
      if(viz.count(a)) break;
      viz.emplace(a);
      if(viz.count(b)) break;
      viz.emplace(b);
      cur+=S[a]+S[b];
//      dump(c,k,a,b,S[a],S[b],cur);
      SMAX(res,cur);
    }
  }
  cout<<res<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>N;
  REP(i,N) cin>>S[i];
  solve();
  
  return 0;
}


Measured memory_bytes: 5168
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int N,T,A,res=0;
	vector<int>H;
	cin>>N>>T>>A;
	A*=1000;
	for(int i=0;i<N;i++)
	{
		int h;
		cin>>h;
		H.push_back(h);
	}
	for(int i=0;i<N;i++)
	{
		res=abs(A-(T*1000-H[res]*6))>abs(A-(T*1000-H[i]*6))?i:res;
	}
	cout<<res+1<<endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
const int N=1e6+1;
int main()
{
	int n,m,i;
	int a,sum=0;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d",&a);
		sum+=a;
	}
	if(sum>n)
	printf("-1");
	else
	printf("%d",n-sum);
}  


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

int main() {
	int N;
	cin >> N;
	
	vector<int> d(N);
	for (int i = 0; i < N; ++i) {
		cin >> d.at(i);
	}
	
	sort(d.begin(), d.end());
	
	int ans = 1;
	for (int i = 0; i < N - 1; ++i) {
		if (d.at(i) < d.at(i + 1)) {
			ans++;
		}
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int N;
	scanf("%d", &N);
	int A[N];
	int i;
	for (i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	int count;
	int flag=0;
	for (count=0; ; count++) {
		for (i = 0; i < N; i++) {
			if (A[i] % 2 != 0) {
				flag=1;
				break;
			}
			A[i] /= 2;
		}
		if (flag == 1) {
			break;
		}
	}
	printf("%d\n", count);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
vector<int> prime;
bool isPrime[250000];

void PrimeCalc()
{
	memset(isPrime, 1, sizeof(isPrime));
	isPrime[0] = isPrime[1] = false;
	for(int i = 2; i < 250000; ++i)
	{
		if(isPrime[i])
		{
			prime.push_back(i);
			for(int j = 2 * i; j < 250000; j += i)
			{
				isPrime[j] = false;
			}
		}
	}
}

void solve()
{
	PrimeCalc();
	int n;
	while(cin >> n, n)
	{
		int ans = 0;
		for(int i = n + 1; i <= 2 * n; ++i)
		{
			if(isPrime[i])
			{
				++ans;
			}
		}
		cout << ans << endl;
	}
}

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

Measured memory_bytes: 1592
#include <stdio.h>

typedef struct Prime {
  int p;
  int cnt;
} P;

//GCD
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}

int main() {
  int n;
  scanf("%d", &n);
  P p[50]; int c=0, m;
  for (int i=2; i<=n; i++) {
    m=i;
    for (int j=0; j<c; j++) {
      if (gcd(m, p[j].p) != 1) {
        while (m % p[j].p == 0) {
          m = m / p[j].p;
          p[j].cnt++;
        }
      }
    }
    if (m != 1) {
      p[c].p = m;
      p[c].cnt = 1;
      c++;
    }
  }
  int ce74 = 0, ce24 = 0, ce14 = 0, ce4 = 0, ce2 = 0;
  for (int i=0; i<c; i++) {
    if (p[i].cnt >= 2) ce2++;
    if (p[i].cnt >= 4) ce4++;
    if (p[i].cnt >= 14) ce14++;
    if (p[i].cnt >= 24) ce24++;
    if (p[i].cnt >= 74) ce74++;
  }
  int ans = 0;
  ans += (ce74 >= 1) ? ce74 : 0;
  ans += (ce24 >= 1) ? ce24*(ce2-1) : 0;
  ans += (ce14 >= 1) ? ce14*(ce4-1) : 0;
  ans += (ce4 >= 2) ? ce4*(ce4-1)*(ce2-2)/2 : 0;
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		char s='#',p='.',n='\n';
		while(true){
			String in=br.readLine();
			if(in.equals("0 0")) break;
			String[] a=in.split(" ");
			int H=Integer.parseInt(a[0]);
	        int W=Integer.parseInt(a[1]);
			for(int i=0;i<H;i++){
				for(int j=0;j<W;j++){
					if(i!=0&&i!=H-1&&j!=0&&j!=W-1){
						sb.append(p);
					}else{
						sb.append(s);
					}
				}
				sb.append(n);
			}
			sb.append(n);
		}
		System.out.print(sb);
	}
}

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

int main(){
    int n, m, x;
    cin >> n >> m >> x;

    int left = 0, right = 0;
    vector<int> a(m);
    for(int i=0; i<m; i++){
        cin >> a[i];
        if(a[i] < x) left += 1;
        if(a[i] > x) right += 1;
    }

    cout << min(left, right) << endl;
    return 0;
}

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() {
    ll x; cin >> x;
    ll ans = 0;
    ll r = x%11;
    if(r==0);
    else if(r<=6) ans++;
    else ans += 2;
    ans += 2*(x/11);
    cout << ans;
}


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

int main(){

    int n;
    int ans=0;
    cin>>n;
    vector<int> p(n);

    for(int i=0;i<n;i++) cin>>p[i];

    for(int i=1;i<n-1;i++){
       // if(p[i]==p[i-1]+p[i]+p[i+1]-min({p[i-1],p[i],p[i+1]})-max({p[i-1],p[i],p[i+1]})) ans++;
        if(p[i]<p[i+1]&&p[i]>p[i-1]||p[i]<p[i-1]&&p[i]>p[i+1]) ans++;
    }

    cout<<ans<<endl;


    return 0;
}

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

using namespace std;

int main()
{
  int n, s, t, u, l;
  string str;

  while(cin>>str){
    n = 0;
    l = str.size();
    for(int i = 0; i < l; ++i){
      if(str[i] == 'J'){
	s = i;
	while(i < l && str[i] == 'J') ++i;
	s = i - s;
	
	t = i;
	while(i < l && str[i] == 'O') ++i;
	t  = i - t;

	if(t == 0 || s < t){
	  --i;
	  continue;
	}
	s = min(s, t);

	u = 0;
	while(u < s && i < l && str[i] == 'I'){++i; ++u;}
	if(u == s) n = max(n, s);
	--i;
      }
    }

    cout << n << endl;
  }

  return 0;
}

Measured memory_bytes: 1964
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long 
#define PB push_back
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define pii pair <int,  int>
#define pll pair <long long , long long>  
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

const ll maxn = 3000 + 10 , N = 3e5 , mod = 998244353;

ll dp[maxn][maxn];

int main() {
    ll a , b , c , d;
    cin >> a >> b >> c >> d;
    dp[a][b] = 1;
    for (int i = b + 1; i < maxn; ++i) {
        dp[a][i] = (dp[a][i - 1] * a) % mod;
    }
    for (int j = a + 1; j < maxn; ++j) {
        dp[j][b] = (dp[j - 1][b] * b) % mod;
    }
    for (int i = a + 1; i < maxn; ++i) {
        for (int j = b + 1;  j < maxn; ++j) {
            dp[i][j] = (dp[i][j] + (dp[i - 1][j] * j)) % mod;
            //  cout << dp[i][j] << endl;
            dp[i][j] = (dp[i][j] + (dp[i][j - 1] * i)) % mod;
            //  cout << dp[i][j] << endl;
            dp[i][j] += mod;
            dp[i][j] -= (((dp[i - 1][j - 1] * (i - 1)) % mod) * (j - 1)) % mod; 
            // cout << dp[i][j] << endl;
            // dp[i][j]--;
            dp[i][j] %= mod;
        }
    }
    // cout << dp[a + 1][b + 1] << endl;
    cout << dp[c][d] << endl;
}

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

int main() {
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N), F(N);
    for (ll& a : A) {
        cin >> a;
    }
    for (ll& f : F) {
        cin >> f;
    }
    sort(A.begin(), A.end(), [](const ll& a, const ll& b) {
        return a > b;
    });
    sort(F.begin(), F.end());

    ll low = -1, high = 1e12;
    while (high - low > 1) {
        ll mid = (high + low) / 2;
        ll cnt = 0;
        for (int i = 0; i < N; i++) {
            if (A[i] * F[i] <= mid) {
                continue;
            } else {
                cnt += A[i] - mid / F[i];
            }
        }

        if (cnt <= K) {
            high = mid;
        } else {
            low = mid;
        }
    }
    cout << high << endl;
}


Measured memory_bytes: 3328
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
const lint MOD = pow(10, 9) + 7;

int main() {

	vector<char>al(26);
	al = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };


	vector<char>AL(26);
	AL = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };


	vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };

	char A;
	cin >> A;
	rep(i, 26) {
		if (al[i] == A) {
			cout << al[i + 1] << endl;
		}
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long f[401][401],sum[401];
int main()
{
    int i,j,n,s,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1];
    }
    for(s=1;s<n;s++)
    { 
        for(i=1;i<=n-s;i++)
        {
            j=s+i;
            f[i][j]=0x7fffffffffffffff;
            for(k=i;k<j;k++)
            {
                f[i][j]=min(f[i][j],f[i][k]+sum[j]-sum[i-1]+f[k+1][j]);
                //printf("---%d %d %d %d\n",i,j,k,f[i][j]);
            }
        }
    }
    //for(i=1;i<n;i++)
        //for(j=1;j<=n;j++)
                //printf("%d %d %d\n",i,j,f[i][j]);
    printf("%lld",f[1][n]);
    return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>a(5,0);
	for(int i=0;i<n;++i){
		string s; cin>>s;
		if(s.front()=='M')++a.at(0);
		else if(s.front()=='A')++a.at(1);
		else if(s.front()=='R')++a.at(2);
		else if(s.front()=='C')++a.at(3);
		else if(s.front()=='H')++a.at(4);
	}
	uint64_t ans=0;
	for(int i=0;i<a.size();++i){
		for(int j=i+1;j<a.size();++j){
			for(int k=j+1;k<a.size();++k){
				ans+=(uint64_t)a.at(i)*a.at(j)*a.at(k);
			}
		}
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("[DEBUG] ");W(__VA_ARGS__);}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1<<20;
void solve() {
    int X;
    R(X);
    if(X<600)W(8);
    else if(X<800)W(7);
    else if(X<1000)W(6);
    else if(X<1200)W(5);
    else if(X<1400)W(4);
    else if(X<1600)W(3);
    else if(X<1800)W(2);
    else if(X<2000)W(1);
}
int main(){
#define MULTITEST 0
#if MULTITEST    
    CASET{
        solve();
    }
#else
    solve();
#endif
    return 0;
}


Measured memory_bytes: 3820
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    string n;
    cin>>n;
    ll sum=0;
    ll k=n.length();
    for(ll i=0;i<k;i++)
    {
        sum+=(n[i]-'0');
    }
    if(sum%9==0)
    {
        cout<<"Yes"<<endl;
    }
    else
        cout<<"No"<<endl;
}

Measured memory_bytes: 3716
L = int(input())
p = []
while L:
    p.append(L % 2)
    L >>= 1
p = p[::-1]
k = 1
ed = []
for i in range(2, len(p) + 1):
    ed.append((i - 1, i, 0))
    ed.append((i - 1, i, k))
    k *= 2
    if p[i - 1]:
        ed.append((1, i, k))
        k += 1
print(len(p), len(ed))
for u, v, w in ed:
    print(u, v, w)

Measured memory_bytes: 38580
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int n,a,b;
  cin >> n >> a >> b;

  cout << ((a * n > b) ? b : a * n);


  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


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

using namespace std;

typedef long long int64;

int main(void){
    int64 N;
    cin>>N;
    vector<pair<int64,int64>> BA(N);
    int64 A,B;
    int64 T=0;
    for(int64 i=0;i<N;i++){
        cin>>A>>B;
        BA[i]=make_pair(B,A);
    }
    sort(BA.begin(),BA.end());

    for(int64 i=0;i<N;i++){
        T+=BA[i].second;
        if(T>BA[i].first){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 3328
n,k = map(int,input().split())
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

fac = [0]*(n+1)
fac[0] = 1
fac[1] = 1
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod

def combi(n,r,mod=10**9+7):
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

ans = 0
for i in range(min(k+1,n)):
    ans += combi(n,i)*combi(n-1,n-i-1) % mod
    ans %= mod
print(ans % mod)

Measured memory_bytes: 43996
#include <cstdio>

constexpr unsigned int InputSize = 3e6;
unsigned char Input[InputSize];
unsigned char* pointer = Input;

inline unsigned int getInt(void){
    unsigned int res = 0; while(*pointer < '0') ++pointer;
    do{
        res = 10 * res + ((*pointer) - '0');
    } while(*(++pointer) >= '0');
    return res;
}

unsigned int n;
unsigned int N;
constexpr unsigned int SIZE = (1U << 19) + 1;
unsigned int data[2 * SIZE];

inline void set(void){
    N = 1; while(N < n) N <<= 1;
    while(*pointer < 'a') ++pointer;
    unsigned int i, j;
    for(i = 0, j = N; i < n; ++i, ++j){ 
        unsigned char idx = *(pointer++) - 'a'; data[j] = 1U << idx;
    }
    for(i = N - 1; i ; --i) data[i] = data[i << 1] | data[(i << 1) | 1U];
}

inline void query(void){
    while(*pointer < '0') ++pointer;
    if(*(pointer++) == '1'){
        unsigned int index = getInt() - 1;
        while(*pointer < 'a') ++pointer;
        unsigned char idx = *(pointer++) - 'a';
        data[index += N] = 1U << idx;
        while(index >>= 1) data[index] = data[index << 1] | data[(index << 1) | 1U];
    }
    else{
        unsigned int l = getInt() + N - 1, r = getInt() + N;
        unsigned int res = 0;
        while(l < r){
            if(l & 1) res |= data[l++]; l >>= 1;
            if(r & 1) res |= data[--r]; r >>= 1;
        }
        printf("%u\n", __builtin_popcount(res));
    }
}

int main(void){
    fread(Input, sizeof(unsigned char), InputSize, stdin);
    n = getInt(); set(); 
    unsigned int q = getInt();
    while(q--) query();
    return 0;
}


Measured memory_bytes: 6400
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CLEAR(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



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

	string s;
	cin >> s;
	bool egg;
	int max_words = -1;
	for (int i = 0, w = 0; i < s.size(); )
	{
		++w;
		int ni = i + (s[i] == 'e' ? 3 : 7);

		if (ni == s.size() || s[i] == s[ni])
		{
			if (w > max_words)
			{
				egg = s[i] == 'e';
				max_words = w;
			}
			w = 0;
		}

		i = ni;
	}
	cout << (egg ? "egg" : "chicken") << endl;
}

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

typedef long double ll;
#define    mod      1000000007
#define    speed    ios_base::sync_with_stdio(false);
#define    up       cin.tie(NULL);
#define    pb       push_back
#define    mp       make_pair
#define    T        int t; cin >> t; while(t--)

ll dp[3005][3005] , arr[3005];
int  n, k;
ll solve(int i , int cnt){
    if(cnt > k ){
        return 0;
    }
    if(i > n){
        return 1.0;
    }
    ll &ans = dp[cnt][i];
    if(ans != -1){
        return ans;
    }
    ll temp1 = (1.0 - arr[i])*solve(i+1 , cnt + 1);
    ll temp2 = arr[i]*solve(i+1 , cnt);
    return (ans = temp1 + temp2);
}

int main(){
   speed up
   for(int i = 0; i <= 3000; i++){
       for(int j = 0; j <= 3000; j++){
           dp[i][j] = -1.0;
       }
   }
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> arr[i];
   }
   k = n/2;
   if(n%2==0){
       k--;
   }
   cout << setprecision(12) << solve(1 , 0) << '\n';
}

Measured memory_bytes: 141440
#include <stdio.h>
int main(){
  int i,n;
  double dx[21],dy[21];
  double x,y,sum=0;
  for(n=0;~scanf("%lf,%lf",&dx[n],&dy[n]);n++);
  dx[n]=dx[0];
  dy[n]=dy[0];
  for (i=0;i<n;i++)
    sum+=(dx[i]-dx[i+1])*(dy[i]+dy[i+1]);
  printf("%f\n",sum/2);
  return 0;
}

Measured memory_bytes: 652
c,i=30,k[30],x;main(n,a)
{
	for(;~scanf("%d",&a);)
	{
		--n&&(x^=a,k[__builtin_popcount(a^a-1)]=1);
	}
	for(;i--;)x&1<<i&&k[i+1]&&(c++,x^=(1<<i+1)-1);
	printf("%d",x?-1:c);
}

Measured memory_bytes: 128
def c_linear_approximation(N, A):
    import numpy
    B = numpy.array([a-k for k, a in enumerate(A)])  # B_k = A_k - k
    b = int(numpy.median(B))  # Bの中央値を選ぶのが最適
    ans = numpy.sum(abs(B - b))  # 実際に悲しみを計算
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

Measured memory_bytes: 29540
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define MOD 1000000007
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 1005

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_rows,num_cols;
ll dp[MAXN][MAXN];

int main(){
    scanf("%d %d",&num_rows,&num_cols);
    dp[1][1] = 1;
    for(int i=1; i<=num_rows; i++){
        for(int k=1; k<=num_cols; k++){
            char c; scanf(" %c",&c);
            if(c == '#') continue;
            if(i != 1 || k != 1) dp[i][k] = (dp[i-1][k]+dp[i][k-1])%MOD;
        }
    }
    printf("%d\n",dp[num_rows][num_cols]);
}


Measured memory_bytes: 8064