akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fe first
#define se second
#define endl "\n"
#define pii pair<int,int>
#define PI  3.14159265358979323846

const int N=1e5+10;
int dp[N][3];

int main()
{  int n,k;
	cin>>n;
    

  for(int i=0;i<n;i++)
    { for(int j=0;j<3;j++)
	 	 cin>>dp[i][j];
	}

   for(int i=n-2;i>=0;i--)
     { dp[i][0]+=max( {dp[i+1][1],dp[i+1][2]} );
       dp[i][1]+=max({dp[i+1][0],dp[i+1][2] });
       dp[i][2]+=max({dp[i+1][0],dp[i+1][1]});
     }


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


     int maxi=max({dp[0][0],dp[0][1],dp[0][2]});
     cout<<maxi;
	   return 0;
 }


Measured memory_bytes: 1408
N=int(input())
*A,=map(int,input().split())
*B,=map(int,input().split())

i=0
ans=0
while i<N:
    if A[i]+A[i+1]>=B[i]:
        ans+=B[i]
        A[i+1]-=max(B[i]-A[i],0)
    else:
        ans+=A[i]+A[i+1]
        A[i+1]=0
    i+=1

print(ans)

Measured memory_bytes: 18476
#include<stdio.h>

int main(){
	
	int n,m=100000,s=0;
	
	scanf("%d",&n);
	
	for(int t=0;t<n;t++){
		
		m=m*1.05;
		
		if(m%1000!=0){
			s=m%1000;
			m=m+1000-s;
		}
		//printf("%d\n",m);
	}
	
	printf("%d\n",m);
	return 0;
}

Measured memory_bytes: 2596
#define MOD 998244353
#define  endll  "\n"
#define  ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 7, M = 2 * N, SEGN = 2 << (32 - __builtin_clz(N));
int n, m;
int cur[N];
bool ever[N], may[N];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input", "rt", stdin);
    //  freopen("output", "wt", stdout);
#endif
    may[1]  = 1;
    cin >> n >> m;
    fill(cur,cur+n+1,1);


    for (int i = 0; i < m; i++) {
        int t, f;
        cin >> t >> f;
        cur[f]++, cur[t]--;
        if (!may[f] && may[t]) may[f] = 1;
        if (cur[t] == 0) may[t] = 0;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        if (may[i])ans++;
    cout << ans;
}

Measured memory_bytes: 4088
#include <iostream>
using namespace std;
int n,q;
int s[200000];
int main(){
    int a,b,c;
    cin >> n >> q;
    for(int i = 1;i < q + 1; i++){
        cin >> a >> b >> c;
        if(a == 0){
            s[b] += c;
        }
        if(a == 1){
            int ans = 0;
            for(int j = b; j < c + 1;j++){
                ans += s[j];
            }
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3472
#include<bits/stdc++.h>
using namespace std;
int main() {
    int h,w;
    cin >> h >> w;
    vector<vector<int>> c(10,vector<int>(10, 0));
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            cin >> c[i][j];
    for (int k = 0; k < 10; k++) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (c[i][k] + c[k][j] < c[i][j])
                    c[i][j] = c[i][k] + c[k][j];
            }
        }

    }
    long long sum = 0;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++) {
            int q;
            cin >> q;
            if(q != -1){
                sum += c[q][1];
            }
        }
    }
    cout << sum << endl;
}

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

using std::pair;
using std::vector;
using std::string;

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

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

string procStatus() {
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

int n, k;
int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    read(n), read(k);
    if(k == 0) {
        printf("%lld\n", 1ll * n * n);
        return 0;
    }

    ll ans = 0;
    for(int i = k+1; i <= n; ++i) {
        ans += (n / i) * (i - k);
        ans += std::max(n % i - k + 1, 0);
    }
    printf("%lld\n", ans);

    return 0;
}


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


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    string str;
    cin>>str;
    int q;
    cin>>q;
    vector<set<int> > vec(26,set < int > ());
    for(int i=0;i<n;++i)
    {
    	vec[str[i]-'a'].insert(i);
    }
    for(int i=0;i<q;++i)
    {
    	int type;
    	cin>>type;
    	if(type==1)
    	{
    		char c;
    		int j;
    		cin>>j>>c;
    		int k=0;
    		for(k=0;k<26;++k)
    		{
    			if(vec[k].find(j-1)!=vec[k].end())
    				break;
    		}
    		vec[k].erase(j-1);
    		vec[c-'a'].insert(j-1);

    	}
    	else
    	{
    		int l,r;
    		cin>>l>>r;
    		int sum=0;
    		for(int k=0;k<26;++k)
    		{
    			
    			auto it1=vec[k].lower_bound(l-1);
    			int index=*it1;
    			if(it1!=vec[k].end())
    			if(index<=(r-1)&&index>=(l-1))
    				sum++;
    		}
    		cout<<sum<<"\n";
    	}
    }

}


Measured memory_bytes: 26268
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

s=ss()
q=ii()

arr=deque(list(s))
chk=0
for i in range(q):
    x=input()
    if x=="1":
        if chk==1:
            chk=0
        else:
            chk=1
    
    else:
        j,k,l=map(str,x.split())

        if chk==0 and k=="1":
            arr.extendleft(deque(list(l)))
            
        elif chk==0 and k=="2":
            arr.extend(deque(list(l)))
        elif chk==1 and k=="1":
            arr.extend(deque(list(reversed(list(l)))))
        elif chk==1 and k=="2":
            arr.extendleft(deque(list(reversed(list(l)))))

if chk==0:
    print("".join(list(arr)))
else:
    print("".join(reversed(list(arr))))


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

int main() {
  string S;
  cin >> S;
  for (int i = 2; i < S.size(); i += 2) {
    int m = (S.size()-i)/2;
    string s1 = S.substr(0, m);
    string s2 = S.substr(m, m);
    if (s1 == s2) {
      cout << m * 2 << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;

int a[100005];
map<int,int>ans;

int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++){
		ans[a[i]]++;
		ans[a[i] + 1]++;
		ans[a[i] - 1]++;
	}
	int sum = -1;
	for(int i = 1;i <= 100004;i++){
		sum = max(ans[i],sum);
	}
	cout << sum;
}

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

int main() {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i<n; i++) {
    cin >> a[i];
  }
  int count = 0;
  for(int i=1; i<=n; i += 2) {
    if(a[i-1] % 2  == 1) count++ ;
  }
  cout << count << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
const long MAX_S = 10;

long calc(long a[MAX_S-1], string s){
    long len = s.size();
    long res = 0;
    long temp = s[0]-'0';
    for(long i=1; i<len; i++){
        if(a[i-1]==1){
            res += temp;
            temp = s[i]-'0';
        }else if(a[i-1]==0){
            temp *= 10;
            temp += s[i]-'0';
        }
    }
    return res+temp;
}

long dfs(long i, long last, long a[MAX_S-1], string s){
    if (i==last) return calc(a, s);
    long res0 = 0, res1 = 0;
    a[i] = 0;
    res0 = dfs(i+1, last, a, s);
    a[i] = 1;
    res1 = dfs(i+1, last, a, s);
    return res0+res1;
}

int main(void){
    string s;
    cin >> s;
    long a[MAX_S-1] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
    printf("%ld\n", dfs(0, s.size()-1, a, s));
    return 0;
}

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

int main(){
    int N;
    cin >> N;
    unordered_set<string> shurui;
    for (int i = 0; i < N; i++){
        string n;
        cin >> n;
        shurui.insert(n);
    }
    cout << shurui.size() << endl;
}

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

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

    string s;
    cin >> s;
    int n = s.size();

    vector<ll> mods(n+1);
    mods[0] = 0;
    map<ll, ll> modsmp;
    ++modsmp[0];
    ll inv10 = 1;
    rep1(i, n+1){
        ll d = s[n-i] - '0';
        mods[i] = (mods[i-1] + d*inv10%2019) % 2019;
        ++modsmp[mods[i]];
        inv10 = (inv10 * 10%2019) % 2019;
    }

    ll res = 0;
    for(auto itr = modsmp.begin(); itr != modsmp.end(); ++itr){
        if(itr->second > 1){
            ll num = itr->second;
            res += num * (num-1) / 2;
        }
    }

    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 5148
import java.util.*;

class Main {

	static Scanner sc;

	static void solve() {
		int qnt = sc.nextInt();
		int legs = sc.nextInt();

		if (4*qnt < legs || legs < 2*qnt || legs % 2 != 0) {
			System.out.println("No");
			return;
		}

		System.out.println("Yes");
	}
    
    public static void main(String args[]) throws Exception {
        sc = new Scanner(System.in);

		solve();
    }
}


Measured memory_bytes: 35624
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
using ll = long long;
int main(){ 
    ll a,b;
    cin>>a>>b;
    for(int i=b-a+1;i<a+b;i++){
        cout<<i<<' ';
    }
    return 0;
}


Measured memory_bytes: 256
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

char S[200000],T[200000];
int num[4],num2[4];
int main() {
    int i;
    int H,W,N;
    int r,c;
    scanf("%d %d %d %d %d",&H,&W,&N,&r,&c);
    r--,c--;
    for (i = 0; i < N; i++) scanf(" %c",&S[i]);
    for (i = 0; i < N; i++) scanf(" %c",&T[i]);

    num2[0] = num2[2] = c,num2[1] = num2[3] = r;
    for (i = 0; i < N; i++) {
        if (S[i] == 'L') num2[0]--;
        else if (S[i] == 'U') num2[1]--;
        else if (S[i] == 'R') num2[2]++;
        else num2[3]++;
        if (num2[0] < 0) break;
        if (num2[2] >= W) break;
        if (num2[1] < 0) break;
        if (num2[3] >= H) break;
        if (T[i] == 'L') {
            if (num2[2] > 0) num2[2]--;
        }
        else if (T[i] == 'U') {
            if (num2[3] > 0) num2[3]--;
        }
        else if (T[i] == 'R') {
            if (num2[0] < W-1) num2[0]++;
        }
        else if (num2[1] < H-1) num2[1]++;
    }
    if (i < N) printf("NO\n");
    else printf("YES\n");

    return 0;
}



Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second 
#define mp make_pair
#define int long long
signed main()
{
    IOS
    int a,b,c; cin>>a>>b>>c;
    int diff = a-b;
    cout<<max(0LL,c-diff)<<endl;
    return 0;
}

Measured memory_bytes: 256
S = gets.chomp

if S.length % 2 == 1 then
  print "No"
else
  ans = "Yes"
  for j in 1..S.length / 2 do
    if S[2 * j-2] != "h" or S[2*j-1] != "i" then
      ans = "No"
    end
  end
  print ans
end


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main(){
    stack<int>S1;
    stack<pair<int,int>>S2;
    char ch;
    int sum=0;
    for(int i=0;cin>>ch;i++){
        if(ch=='\\')S1.push(i);
        else if(ch=='/'&&S1.size()>0){
            int j=S1.top();
            S1.pop();
            sum+=i-j;
            int a=i-j;
            while(S2.size()>0&&S2.top().first>j){
                a+=S2.top().second;S2.pop();
            }
            S2.push(make_pair(j,a));
        }
    }
    
    vector<int> ans;
    while(S2.size()>0){ans.push_back(S2.top().second);S2.pop();}
    reverse(ans.begin(),ans.end());
    cout<<sum<<endl;
    cout<<ans.size();
    for(int i=0;i<ans.size();i++){
        cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3232
MOD = 998244353
N, K = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(K)]
lr.sort()

dp = [0]*(N+1)
dp[1] = 1

dpsum = [0]*(N+1)
dpsum[1] = 1

for i in range(2, N+1):
    for l, r in lr:
        li = max(0, i-r)
        ri = i-l
        if ri < 0:
            continue
        dp[i] += dpsum[ri]-dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] += dp[i]+dpsum[i-1]
    dpsum[i] %= MOD

print(dp[N])


Measured memory_bytes: 77016
# -*- coding: utf-8 -*-
# C

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

x, n = map(int, input().split())
p =list(map(int, input().split()))

if n == 0:
    print(x)
    sys.exit()

all = list(range(102))
val = 10000000000
# print(list(set(all) - set(p)))

for a in list(set(all) - set(p)):
    if abs(a - x) < val:
        ans = a
        val = abs(a - x)
        # print(val)
print(ans)


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define pb push_back

using namespace std;

typedef long long ll;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

#define MAX 100100
int n, A[MAX];

const ll mod = 1000000007LL;

void solve() {
  map<int,int> mp;
  ll ans = 1;
  ll rem = 3;
  rep(i,n) {
    ll v;
    if( A[i] == 0 ) {
      v = rem;
      --rem;
    } else {
      v = mp[A[i]-1] - mp[A[i]];
    }
    ( ans *= v ) %= mod;
    ++mp[A[i]];
  }
  cout << ans << endl;
}

int main() {
  cin >> n;
  rep(i,n) cin >> A[i];
  solve();
  return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
/**
 * sqrt(a)+sqrt(b)<sqrt(c)
 * a+2sqrt(ab)+b<c
 * 2sqrt(ab)<c-a-b
 * 因为sqrt(ab)>=0 所以当c-a-b>0时
 * 存在yes 
 * 两边开方得 
 * 4ab<(c-a-b)^2
 * 所以(c-a-b)^2>4ab时  存在yes
 */
#define eps 1e-11
long long n,m;
int main(){
	long long a,b,c;
	cin>>a>>b>>c;
	long long d=c-a-b;
	if(d>0&&d*d>4*a*b){
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}

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

char map[1000][1000];
int h,w,res;

void dfs(int x, int y, char c) {
    if(x<0 || y<0 || x>=w || y>=h) return;
    if(map[y][x] == c) {
        map[y][x] = '.';
        dfs(x-1,y,c); dfs(x,y-1,c);
        dfs(x+1,y,c); dfs(x,y+1,c);
    }
}

int main(void) {
    while(true) {
        res = 0;
        memset(map, 0, sizeof(map));

        scanf("%d%d",&h,&w);
        if(!h && !w) break;
        for(int i=0; i<h; i++) scanf("%s",map[i]);

        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++)
                if(map[i][j] != '.') {
                    res++;
                    dfs(j, i, map[i][j]);
                }
        printf("%d\n", res);

    }
    return 0;
}

Measured memory_bytes: 2324
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    std::ios::sync_with_stdio(false);

    int N; int A; int B;
    cin >> N >> A >> B;
    if (N * A < B)
        cout << N * A << endl;
    else
        cout << B << endl;    
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int n, m;
	long long x = 1, y;
	long long ans = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		x = x * 2;
	}
	y = (100 * (n - m)) + (1900 * m);
	ans = x * y;
	cout << ans;
	return 0;
}

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

typedef pair<int, int> pii;

const int maxn = 2e5 + 10;

int n, m;

set<pii> edges;

bool solve() {
    for(int v = 2; v < n; ++v)
	if(edges.find({1, v}) != edges.end() && edges.find({v, n}) != edges.end())
	    return true;

    return false;
}

int main() {
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= m; ++i) {
	int a, b;

	scanf("%d %d", &a, &b);

	edges.insert({a, b});
	edges.insert({b, a});
    }

    if(solve())
	printf("POSSIBLE\n");
    else
	printf("IMPOSSIBLE\n");

    return 0;
}


Measured memory_bytes: 18944
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <map>

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


int main()
{
	int n;
	cin >> n;
	REP(i, n){
		int a[3];
		cin >> a[0] >> a[1] >> a[2];
		sort(a, a + 3);
		string ans = a[2] * a[2] == a[1] * a[1] + a[0] * a[0] ? "YES" : "NO";

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

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#ifdef _debug
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#define dout(i) 0&&0
#endif
#define rout(i) (cout << i << '\n', 0)
using ll = long long;
using ull = unsigned long long;
using ul = unsigned;
using db = double;
template<typename T, typename S>
inline istream& operator >> (istream &in, const pair<T, S> &a){
	return in >> a.first >> a.second;
}
template<typename T, typename S>
inline ostream& operator << (ostream &ou, const pair<T, S> &b){
	return ou << b.first << ' ' << b.second;
}

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int a, b;
	cin >> a >> b;
	cout << max(0, a-b-b);
}

Measured memory_bytes: 256
class BST:
  def __init__(self):
    self.root = None
  
  def insert(self, data):
    z = Node(data)
    y = None
    x = self.root

    while x:
      y = x
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    z.parent = y
    if y == None:
      self.root = z
    elif z.data < y.data:
      y.left = z
    else:
      y.right = z

  def find(self, data):
    x = self.root
    z = Node(data)
    while x and data != x.data:
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    return x
    """if x is not None:
      return True
    else:
      return False"""

  def getMinimum(self, z):
    while z.left:
      z = z.left
    return z

  def getSuccessor(self, z):
    if z.right:
      return self.getMinimum(z.right)
    
    y = z.parent
    while y and z == y.right:
      z = y
      y = y.parent
    return y
      
  def delete(self, data):
    z = self.find(data)
    if z is None:
      return 

    #z = Node(data)
    if (z.left is None) or (z.right is None):
      y = z
    else:
      y = self.getSuccessor(z)

    if y.left is not None:
      x = y.left
    else:
      x = y.right
    
    if x is not None:
      x.parent = y.parent

    if y.parent is None:
      self.root = x
    elif y == y.parent.left:
      y.parent.left = x
    else:
      y.parent.right = x

    if y != z:
      z.data = y.data

  def print(self):
    print('',' '.join(map(str, self.root.inorder())))
    print('',' '.join(map(str, self.root.preorder())))


class Node():
  def __init__(self, data):
    self.data = data
    self.left, self.right = None, None

  def inorder(self):
    in_list = []
    if self.left:
      in_list += self.left.inorder()
    in_list += [self.data]
    if self.right:
      in_list += self.right.inorder()
    return in_list
  
  def preorder(self):
    pre_list = []
    pre_list += [self.data]
    if self.left:
      pre_list += self.left.preorder()
    if self.right:
      pre_list += self.right.preorder()
    return pre_list

tree = BST()
n = int(input())
for _ in range(n):
  inp = input().split()
  if len(inp) == 2:
    if inp[0] == "insert":
      tree.insert(int(inp[1]))
    elif inp[0] == "find":
      x = tree.find(int(inp[1]))
      if x is not None:
        print("yes")
      else:
        print("no")
    else:
      tree.delete(int(inp[1]))
  else:
    tree.print()



Measured memory_bytes: 117248
N = int(input())
xyh = [list(map(int,input().split())) for _ in range(N)]
xyh.sort(key=lambda x:-x[2])
for cx in range(101):
    for cy in range(101):
        H = 0
        ok = True
        for i in range(N):
            x,y,h = xyh[i]
            if h != 0:
                if H == 0:
                    H = h+abs(cx-x)+abs(cy-y)
                else:
                    ok = H==h+abs(cx-x)+abs(cy-y)
            else:
                ok = abs(cx-x)+abs(cy-y)-H>=0
            if not ok:
                break
        if ok:
            break
    if ok:
        break
    
print('{} {} {}'.format(cx,cy,H))

Measured memory_bytes: 3064
def LI():
  return list(map(int, input().split()))

N = int(input())
P = LI()
Q = LI()

result = []
def permutations(N, cur):
  if len(cur) == N:
    result.append(cur)
    return

  for i in range(1, N+1):
    if i not in cur:
      permutations(N, cur+[i])

permutations(N,[])
result.sort()
print(abs(result.index(P) - result.index(Q)))

Measured memory_bytes: 82156
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <vector <int>> vii;
typedef vector <long long> vll;
typedef vector <string> vs;
typedef vector <char> vc;
typedef set <int> si;
typedef set <string> ss;
typedef queue <int> qi;
typedef queue <long long> qll;
typedef queue <string> qs;
typedef queue <char> qc;
typedef struct board board;
typedef pair <int, int> pi;
typedef pair <long long, long long> pll;
typedef pair <int, pair<int, int>> pii;

#define eb emplace_back
#define ppb pop_back
#define clr(a) a.clear()
#define F first
#define S second
#define mkp make_pair

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define left(x) x * 2
#define right(x) x * 2 + 1

#define meme(a, b, c) fill(a + 1, a + 1 + b, c)

#define max(a, b) (a > b ? a : b)
#define min(a, b) (a > b ? b : a)
#define abs(a) (a > 0? a : -(a))

#define move(s) s += "#"

#define eprintf(...) fprintf(stderr, __VA_ARGS__);

template <typename T>
void printArr(const T * arr, int s, int fn) {
    for (int i = s; i <= fn; ++ i) cout << arr[i] << " ";
    cout << '\n';
}

template <typename T>
long long minArr(const T * arr, int s, int fn) {
    ll res = 1e16 + 1;
    for (int i = s; i <= fn; ++ i) {
        res = min(res, arr[i]);
    }
    return res;
}

template <typename T>
void printVec(const T * arr) {
    for (int i = 0; i < sz(arr); ++ i) cout << arr[i] << " ";
    cout << '\n';
}

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

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

void to_pray() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cerr << "Ready\n";
}

const int N = 1e5 + 10;
const int NN = 1e3 + 10;
const int NNN = 2e3 + 9;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e12 + 7;
const int EPS = 1e-9 - 8;
const int vN = 2e4 + 10;
const int sz = (1 << 22) - 1;
const double PI = acos(-1);

int a[N];

int main () {
    to_pray();

    int n;
    cin >> n;

    int mx = 0, ans = 0;

    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        if (i == 1)continue;
        if (a[i] <= a[i - 1])
            ++ans;
        else {
            mx = max(ans, mx);
            ans = 0;
        }
    }

    mx = max(mx, ans);

    cout << mx;

    //eprintf("%.18lf seconds\n", (double)clock() / CLOCKS_PER_SEC);

    cout << '\n';
    
    return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main(){
  int N;
  cin >> N;
  
  string S;
  int count[4] = {};
  while (cin >> S){
    if(S == "AC") count[0] ++;
    else if(S == "WA") count[1] ++;
    else if(S == "TLE") count[2] ++;
    else if(S == "RE") count[3] ++;
  }
  cout << "AC x " << count[0] << endl;
  cout << "WA x " << count[1] << endl;
  cout << "TLE x " << count[2] << endl;
  cout << "RE x " << count[3] << endl;
    
  return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>

int n, m;
int jew_x[21];
int jew_y[21];
char dir;
int amo;

int main(void)
{
	int i, j;
	int my_x, my_y;
	int map[21][21];
	
	while (1) {
		
		my_x = my_y = 10;
		
		for( i=0; i<21; i++ ){
			for( j=0; j<21; j++ ){
				map[i][j] = 0;
			}
		}
		
		scanf( "%d", &n );
		if ( n == 0 ) break;
		
		for( i=0; i<n; i++ ) {
			scanf( "%d %d", &jew_x[i], &jew_y[i] );
		}
		
		scanf( "%d", &m );
		for( i=0; i<m; i++ ) {
			scanf( "%*c%c %d", &dir, &amo );
			switch(dir) {
			
				case 'N':
					for( j=0; j<amo; j++ ) {
						my_y++;
						map[my_y][my_x] = 1;
					}
					break;
				
				case 'S':
					for( j=0; j<amo; j++ ) {
						my_y--;
						map[my_y][my_x] = 1;
					}
					break;
				
				case 'E':
					for( j=0; j<amo; j++ ) {
						my_x++;
						map[my_y][my_x] = 1;
					}
					break;
				
				case 'W':
					for( j=0; j<amo; j++ ) {
						my_x--;
						map[my_y][my_x] = 1;
					}
					break;
			}
			
		}
		
		for( i=0; i<n; i++ ) {
			if ( map[jew_y[i]][jew_x[i]] == 0 )
				break;
		}
		
		if ( i == n ) printf( "Yes\n" );
		else printf( "No\n" );
	}
	
	return 0;
}

Measured memory_bytes: 584
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int read()
{
	int a = 0,x = 1;
	char ch = getchar();
	while(ch > '9' || ch < '0'){
		if(ch == '-') x = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		a = a*10 + ch-'0';
		ch = getchar();
	}
	return a*x;
}
const int N=107;
int n;
int sum[N];

int main()
{
	n = read();
	for(int i = 1;i <= n;i ++){
		int a = read(),b = read();
		sum[i] = sum[i-1] + (a==b);
	}
	for(int i = 3;i <= n;i ++){
		if(sum[i]-sum[i-3] >= 3) {
			printf("Yes");
			return 0;
		}
	}
	printf("No");
	return 0;
}

Measured memory_bytes: 1600
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n;
    cin>>n;
    set<int> x;
    forn(i,n){
        int a;
        cin>>a;
        x.insert(a);
    }
    cout<<x.size()<<endl;
    return 0;
}



Measured memory_bytes: 3596
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
ll n,k,a[MAXN],f[MAXN];
bool check(ll mx)
{
	ll t=k;
	for(int i=1;i<=n;++i)
	{
		int j=n+1-i;
		ll x=mx/f[j];
		t-=max(0LL,a[i]-x);
		if(t<0)
			return false;
	}
	return true;
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		f[i]=read();
	ll L=0,R=(ll)(1e12),res;
	sort(a+1,a+1+n);
	sort(f+1,f+1+n);
	while(L<=R)
	{
		ll mid=(L+R)>>1;
		if(check(mid))
			res=mid,R=mid-1;
		else
			L=mid+1;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3328
#include <iostream>

using namespace std;

/* 
hon when the digit in the one's place of N is 2 4 5 7 9
pon when the digit in the one's place of N is 0 1 6 8
bon when the digit in the one's place of N is 3
*/
int main () {
  int n;
  cin >> n;
  int rem = n % 10;
  if (rem == 2 || rem == 4 || rem == 5 || rem == 7 || rem == 9) {
    cout << "hon\n";
  } else if (rem == 0 || rem == 1 || rem == 6 || rem == 8) {
    cout << "pon\n";
  } else {
    cout << "bon\n";
  }
  return 0;
}
      

Measured memory_bytes: 3524
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:256000000")
#include<utility>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

//4Head
#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(NULL));

// belik's shit
ll const mod = 1e9 + 7;
namespace {
	ll mult(ll a, ll b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) {
			val += mod;
		}
		if (val >= mod) {
			val -= mod;
		}
		return val;
	}
	ll poww(ll a, ll b)
	{
		ll val = 1;
		a %= mod;
		while (b > 0){
			if (b % 2) val = mult(a, val);
			a = mult(a, a);
			b >>= 1;
		}
		return val % mod;
	}
	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

ll const maxn = 2e3 + 5;


ll dp[maxn][maxn];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m; cin >> n >> m;
	vector<ll>a(n + 1), b(m + 1);
	a[0] = -1; b[0] = -2;
	for (ll i = 1; i <= n; i++) cin >> a[i];
	for (ll i = 1; i <= m; i++) cin >> b[i];
	dp[0][0] = 1;
	for (ll i = 0; i <= n; i++) {
		for (ll j = 0; j <= m; j++) {
			(dp[i][j] += (i ? dp[i - 1][j] : 0)) %= mod;
			(dp[i][j] += (j ? dp[i][j - 1] : 0)) %= mod;
			(dp[i][j] -= (i && j ? dp[i - 1][j - 1] : 0)) %= mod;
			if (dp[i][j] < 0) dp[i][j] += mod;
			if (a[i] == b[j]) {
				(dp[i][j] += (i && j ? dp[i - 1][j - 1] : 0)) %= mod;
			}
			ll tt = 0;
		}
	}
	cout << (dp[n][m])%mod << endl;
	return 0;

}
/*

*/

Measured memory_bytes: 31616
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;

//#define int long long
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define PI (acos(-1))
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

constexpr ll N_MAX = 100000;
constexpr ll A_I_MAX = 100000;

ll N;
vector<ll> A;

void input() {
	scanf("%lld", &N);
	A.assign(N,0);
	rep(i, N) scanf("%lld", &A[i]);
	sort(all(A));
}

void solve() {
	ll ans = 0;
	ll a=-1;
	rep(i,N){
		if(A[i]==a)ans++;
		else a=A[i];
	}
	if(ans%2)ans++;
	printf("%lld\n", N-ans);
}

signed main() {
	input();
	solve();
	return 0;
}


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

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

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

constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};

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

    int n, m;
    cin >> n >> m;
    vector<ll> S(n + 1);
    S[0] = 0;
    ll ans = 0;
    map<ll, int> mp;
    mp[0] = 1;
    for(int i = 0; i < n; ++i){
        cin >> S[i + 1];
        S[i + 1] += S[i];
        S[i + 1] %= m;
        ans += mp[S[i + 1]];
        ++mp[S[i + 1]];
    }
    cout << ans << endl;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

int p,q,a,n;

int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}

int dfs(int denom,int numer,int prev,int product,int num){
    if(num==0){
        int g=gcd(denom,numer);
        denom/=g;
        numer/=g;
        if(denom==q and numer==p) return 1;
        return 0;
    }

    {
        int tmp1=denom*prev,tmp2=numer*prev+denom*num;
        if((double)tmp2/tmp1<(double)p/q) return 0;
    }

    if((double)numer/denom>(double)p/q) return 0;

    int res=0,x=prev;
    while(true){
        if(product*x>a) break;
        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);
        ++x;
    }
    return res;
}

void solve(){
    while(cin >> p >> q >> a >> n){
        if(p==0 and q==0 and a==0 and n==0) break;
        int g=gcd(p,q);
        p/=g;
        q/=g;

        int ans=0;
        rep(i,1,n+1) ans+=dfs(1,0,1,1,i);
        cout << ans << endl;
    }
}

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

Measured memory_bytes: 3072
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define ll long long

int main()
{
	int N;
	ll K;
	vector<pair<int, int>> vp;
	cin >> N >> K;
	REP(i, 0, N) {
		int a, b;
		cin >> a >> b;
		vp.push_back(make_pair(a, b));
	}
	sort(vp.begin(), vp.end());

	ll cnt = 0;
	REP(i, 0, vp.size()) {
		cnt += vp[i].second;
		if (cnt >= K) {
			cout << vp[i].first << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1400
fun main(args: Array<String>){
    val s = readLine()!!
    var cnt0 = 0
    var cnt1 = 0
    for(i in 0..(s.length - 1)){
        if(s[i] == '0') cnt0++
        else cnt1++
    }
    println(listOf(cnt0, cnt1).min()!! * 2)
}


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

int main() {
  int N;
  cin >> N;
  vector<int> H(N,0);
  for (int i=0;i<N;i++){
    cin >> H.at(i);
  }
  vector<int> DP(N,0);
  DP.at(1)=abs(H.at(1)-H.at(0));
  for (int i=2;i<N;i++){
    DP.at(i)=min(DP.at(i-1)+abs(H.at(i)-H.at(i-1)),DP.at(i-2)+abs(H.at(i)-H.at(i-2)));
  }
  cout << DP.at(N-1) << endl;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int n,x[110];

// Description: ??°??????????????????(?????????????°??????¨???)
// Verifyed: Many Diffrent Problem 

//Appropriately Changed
using edge=struct{int to;};
using G=vector<vector<edge>>;

//Appropriately Changed
void add_edge(G &graph,int from,int to){ 
	graph[from].push_back({to});
	graph[to].push_back({from});
}

// Description: 2??¨??°???????????????????????§??????????????°
// TimeComplexity: $ \mathcal{O}(EV) $ 
// Verifyed: AOJ GRL_7_A

int bipartite_matching(const G &graph){
	int res=0,n=graph.size();
	vector<int> match(n,-1),used(n,0);

	auto dfs=[&](int v){
        auto func=[&](int v,auto func)->int{
        	used[v]=true;
			for(auto &e:graph[v]){
				const int u=e.to,w=match[u];
				if(w<0||(!used[w] && func(w,func))){
					match[v]=u,match[u]=v;
					return true;
				}
			}
			return false;
        };
        return func(v,func);
    };

	rep(v,n){
		if(match[v]>=0) continue;
		fill(_all(used),false);
		if(dfs(v)) res++;
	}
	return res;
}


int main(void){
	cin >> n;
	rep(i,n) cin >> x[i];
	
	vector<int> ans;
	G ograph(2*n);
	
	rep(i,n)rep(j,n){
		if(i==j or x[j]%x[i]) continue;
		add_edge(ograph,i,j+n);
	}

	const int all=n-bipartite_matching(ograph);
	//cout << all << endl;

	rep(loop,all){
		rep(i,n){
			bool ok=true;			
			for(auto &it:ans){
				if(it==i) ok=false;
				if(x[i]%x[it]==0) ok=false;
				if(x[it]%x[i]==0) ok=false;
			}

			if(ok==false) continue;			
			ans.push_back(i);
			
			int y[110],m=0;

			rep(j,n){
				bool can=true;
				for(auto &it:ans){
					if(it==j) can=false;
					if(x[j]%x[it]==0) can=false;
					if(x[it]%x[j]==0) can=false;
				}
				if(can) y[m++]=x[j];
			}

			G graph(2*m);
			rep(j,m)rep(k,m){
				if(j==k or y[k]%y[j]) continue;
				add_edge(graph,j,k+m);
			}

			const int cur=m-bipartite_matching(graph);
			//cout << cur << endl;
			if(ans.size()+cur>=all) break;
			ans.pop_back();
		}
	}


	bool first=true;
	for(auto &it:ans) cout << (first?"":" ") << it+1,first=false;
	cout << endl;

	return 0;
}

Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
string res;
inline void lcs(string s, string t){
  int n = s.length(), m = t.length();
  int dp[n+1][m+1];
  memset(dp, 0, sizeof(dp));
  for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= m; j++){
      if(s[i-1] == t[j-1])
        dp[i][j] = 1 + dp[i-1][j-1];
      else
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
  }
  int i = n, j = m;
  while(i > 0 && j > 0){
    if(s[i-1] == t[j-1]){
      res.push_back(s[i-1]);
      i--;
      j--;
    }
    else if(dp[i-1][j] > dp[i][j-1])
      i--;
    else
      j--;
  }
}
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  lcs(s, t);
  if(res.size() == 0)
    return 0;
  else{
    reverse(res.begin(), res.end());
  	cout << res;
  }
}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int) (n); i++)
#define  itn int
using ll=int64_t;
using vi = vector<int>;
using vll = vector<ll>;



int main(){
  int k;
  string s;
  cin>>k>>s;
  if(s.size()<=k) cout<<s;
  else {rep(i,k){cout<<s.at(i);}
 cout<<"...";} 

}


Measured memory_bytes: 3628
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]

A,B,C,K = read_int_map()
if K <= A:
    print(K)
elif K <= A + B:
    print(A)
else:
    minus = K - (A+B)
    print(A - minus)

Measured memory_bytes: 61720
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>
#include <set>
#include <numeric>

using namespace std;

template <typename T>
using TABLE = vector<vector<T>>;

long long PRIME = 1e9 + 7;
long long PRIME2 = 998244353;


int main(){
    long long A, B, N;
    cin >> A >> B >> N;

    long long q = min(N, B - 1);
    long long k = A * q / B;
    cout << k;

}


//int main(){
//    long long N, M ,Q;
//    cin >> N >> M >> Q;

//    vector<long long> a(Q), b(Q), c(Q), d(Q);
//    for(int i = 0;i < Q; ++i){
//        cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
//    }


//}


Measured memory_bytes: 3676