akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

int ABS(int a){
	return a >= 0 ? a : -a;
}

int main(){
	int N, i, sum = 0, now = 1000000000, ans;
	scanf("%d", &N);
	int *a = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
		sum += a[i];
	}
	for(i = 0; i < N; i++){
		if(ABS(N * a[i] - sum) < now){
			now = ABS(N * a[i] - sum);
			ans = i;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define g(a, b) __gcd((a), (b))
#define l(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T, class U>T rem(T a, U b) { return a - b*floor(a/b); }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        vll A(N);
        rep(i, 0, N) cin >> A[i];

        ll g = 0;
        ll ans = 0;
        rep(i, 0, N) {
                g = g(g, A[i]);
        }
        if (g % 2 == 1) {
                cout << 0 << endl;
        } else {
                while (true) {
                        g /= 2;
                        ++ans;
                        if (g % 2 != 0) break;
                }
                cout << ans << endl;
        }
}

Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D: We Love ABC
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int MOD = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

char s[MAX_N + 4];
ll dp[MAX_N + 1][4];

/* subroutines */

inline void addmod(ll &a, ll b) { a = (a + b) % MOD; }

/* main */

int main() {
  scanf("%s", s);

  dp[0][0] = 1;
  int n = 0;

  for (; s[n]; n++) {
    int k = (s[n] == '?') ? 0 : s[n] - 'A' + 1;
    if (k > 0) {
      for (int i = 0; i < 4; i++) dp[n + 1][i] = dp[n][i];
      addmod(dp[n + 1][k], dp[n][k - 1]);
    }
    else {
      for (int i = 0; i < 4; i++) dp[n + 1][i] = (dp[n][i] * 3) % MOD;
      for (int i = 1; i < 4; i++) addmod(dp[n + 1][i], dp[n][i - 1]);
    }
  }

  printf("%lld\n", dp[n][3]);
  return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define ld long double
typedef pair<ll,ll> pll;
typedef pair<pll,pll> ppll;
typedef vector <ll> vi;
#define out(x) return cout<<x,0;
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define lc(n) 2*n+1
#define rc(n) 2*n+2
#define fill(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL)); 
const ll M = 1e9 + 7;

int main() {
    FAST;
    ll n, x = 0, y = 0, k, i, t, ans = 0, j, c = 0, z = 0, m;
    string s, s1, s2;
    cin >> s >> s1;
    cin >> n >> m;
    cin >> s2;
    if ( s2 == s ) n--;
    if ( s2 == s1) m --;
    cout << n << " "<< m; 

}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	vector<int>x(N), y(M);
	rep(i, 0, N)cin >> x[i]; rep(i, 0, M)cin >> y[i];

	int a(0), b(0);

	rep(i, 0, N)(a += (i*x[i] - (N - 1 - i)*x[i])) %= MOD;
	
	rep(i, 0, M)(b += (i*y[i] - (M - 1 - i)*y[i])) %= MOD;

	cout << (a*b) % MOD << endl;


	return 0;
}

Measured memory_bytes: 1792
import math

X=int(input())

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = int(math.sqrt(n)) +1
    for p in range(3, m, 2): 
        if n % p == 0:
            return False
    return True

def nextprime(n):
    if n < 2:
        return 2
    if n < 7:
        return {2: 3, 3: 5, 4: 5, 5: 7, 6: 7}[n]
    nn = 6*(n//6)
    if nn == n:
        n += 1
        if isprime(n):
            return n
        n += 4
    elif n - nn == 5:
        n += 2
        if isprime(n):
            return n
        n += 4
    else:
        n = nn + 5
    while 1:
        if isprime(n):
            return n
        n += 2
        if isprime(n):
            return n
        n += 4

print(X if isprime(X) else nextprime(X))

Measured memory_bytes: 3064
H,W=[int(i) for i in input().split()]
res = 10**15

for i in range(H):
    a = i*W
    # split vertical
    h = H-i
    w = W//2
    abc = [a, h*w, h*(W-w)]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Hu",i,abc,res)
    # split holizontal
    h2 = h//2
    abc = [a, h2*W, (h-h2)*W]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Hd",i,abc,res)

for i in range(W):
    a = H*i
    # split holizontal
    h = H//2
    w = W-i
    abc = [a, h*w, (H-h)*w]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Wu",i,abc,res)
    # split vertical
    w2 = w//2
    abc = [a, H*w2, H*(w-w2)]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Wd",i,abc,res)

print(res)


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

int a;
int main() {
	while (cin >> a, a) {
		for (int b = 0; b < 9; b++) {
			int c;
			cin >> c;
			a -= c;
		}
		cout << a << endl;
	}
}

Measured memory_bytes: 3096
#include<iostream>
using namespace std;
#include<stdio.h>
int main(void)
{
	int i,f=0,n=0,g=0,a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;
	f=b/d;
	g=c/e;
	if(f>g){
		if(b%d==0)
		cout<<a-f<<endl;
		else
		cout<<a-f-1<<endl;
	}
	else{
		if(c%e==0)
		cout<<a-g<<endl;
		else
		cout<<a-g-1<<endl;
	}
	return 0;
}



Measured memory_bytes: 3048
{-# LANGUAGE BangPatterns #-}
import Control.Arrow (second)
import Control.Monad
import Control.Monad.Fix
import Data.Foldable (foldl')
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)

uread :: VUM.Unbox a => Int -> VUM.IOVector a -> a
uread i v = accursedUnutterablePerformIO $ VUM.unsafeRead v i

uwrite :: VUM.Unbox a => Int -> a -> VUM.IOVector a -> VUM.IOVector a
uwrite i a v = accursedUnutterablePerformIO $ VUM.unsafeWrite v i a >> return v

uswap :: VUM.Unbox a => Int -> Int -> VUM.IOVector a -> VUM.IOVector a
uswap i j v = accursedUnutterablePerformIO $ VUM.unsafeSwap v i j >> return v

ufreeze :: VUM.Unbox a => VUM.IOVector a -> VU.Vector a
ufreeze v = accursedUnutterablePerformIO $ VU.unsafeFreeze v

uthaw :: VUM.Unbox a => VU.Vector a -> VUM.IOVector a
uthaw v = accursedUnutterablePerformIO $ VU.unsafeThaw v

newtype UnionFind = UnionFind (VUM.IOVector Int, VUM.IOVector Int)

findUF :: UnionFind -> Int -> Int
findUF (UnionFind (elems, _)) k = fix
  ( \f (elems, k, path) -> case uread k elems of
    n | n == k -> foldl' (\acc p -> uwrite p n acc) elems path `seq` n
    n          -> f (elems, n, n : path)
  )
  (elems, k, [k])

sizeUF :: UnionFind -> Int -> Int
sizeUF (UnionFind (_, sizes)) i = uread i sizes

uwriteElem :: Int -> Int -> UnionFind -> UnionFind
uwriteElem i a (UnionFind (elem, sizes)) = UnionFind (uwrite i a elem, sizes)

uwriteSize :: Int -> Int -> UnionFind -> UnionFind
uwriteSize i a (UnionFind (elem, sizes)) = UnionFind (elem, uwrite i a sizes)

unionUF :: UnionFind -> Int -> Int -> (UnionFind, Int)
unionUF uf i j =
  let pi  = findUF uf i
      pj  = findUF uf j
      si  = sizeUF uf pi
      sj  = sizeUF uf pj
      sij = si + sj
  in  if pi == pj
        then (uf, 0)
        else
          let (t1, t2) = if si < sj then (pi, pj) else (pj, pi)
          in  ( uwriteSize t1 0 $ uwriteSize t2 sij $ uwriteElem t1 t2 uf
              , si * sj
              )

comb2 k = k * (k - 1) `div` 2

solve :: Int -> Int -> VU.Vector (Int, Int) -> VU.Vector Int
solve n m abs = ufreeze $ (\(_, _, acc) -> acc) $ VU.foldr'
  go
  (group, 0, accursedUnutterablePerformIO $ VUM.replicate m 0)
  abs
 where
  go (a, b) (uf, k, acc) =
    let (uf', d) = unionUF uf a b
        prev     = if k == 0 then 0 else uread (k - 1) acc
    in  (uf', k + 1, uwrite k (prev + d) acc)

  nC2 = comb2 n

  group :: UnionFind
  group = UnionFind
    (uthaw $ VU.enumFromN 0 n, accursedUnutterablePerformIO $ VUM.replicate n 1)

main = do
  let readInt = fmap (second B.tail) . B.readInt

  nm  <- VU.unfoldrN 2 readInt <$> B.getLine
  abs <- VU.replicateM
    (nm VU.! 1)
    (   (\vec -> (vec VU.! 0 - 1, vec VU.! 1 - 1))
    .   VU.unfoldrN 2 readInt
    <$> B.getLine
    )

  let solutions = solve (nm VU.! 0) (nm VU.! 1) abs
  let nC2       = comb2 $ nm VU.! 0

  mapM_ (print . (nC2 -) . (solutions VU.!)) [nm VU.! 1 - 2, nm VU.! 1 - 3 .. 0]
  print nC2


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

using namespace std;

const int N = 85;

int n;
int a[N];

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	
	long long money = 1000, i = 1;
	for (int j = i + 1; j <= n; ++j)
	{
		if (a[j] > a[i]) money += (a[j] - a[i]) * (money / a[i]);
		i = j;
	}
	
	cout << money << '\n';
	
	return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000
#define LL long long
int a[maxn+5],f[maxn+5],n; LL k;
bool check(LL x){
	LL ans=0;
	for(int i=0;i<n;i++){
		ans+=max(0ll,a[i]-x/f[i]);
	}
	return ans<=k;
}
int main(){
	scanf("%d%lld",&n,&k);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<n;i++)scanf("%d",f+i);
	sort(f,f+n);sort(a,a+n,greater<int>());
	LL l=0,r=1e12,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",l);
	return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <math.h>

int main(void){
    int n,count=0;
    int ax[205],ay[205],bx[205],by[205];
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d%d",&ax[i],&ay[i]);
    }    
    for(int i=1; i<=n; i++){
        scanf("%d%d",&bx[i],&by[i]);
    }

    //blueのyソート
    for(int i=1; i<=n; i++){
        int temx=bx[i],temy=by[i],temp=0;
        for(int j=i+1; j<=n; j++){
            if(temy > by[j]){
                temx=bx[j],temy=by[j],temp=j;
            }
        }
        if(temp){
            bx[temp]=bx[i],by[temp]=by[i];
            bx[i]=temx,by[i]=temy;
        }
    }

    for(int i=1; i<=n; i++){
        int temx=-1, temy=-1, temp=0;
        //blueのi※
        for(int j=1; j<=n; j++){
            //redのチェック
            if(ax[j]<bx[i] && ay[j]<by[i]){
                if(temx < ax[j]){
                    temx=ax[j],temy=ay[j],temp=j;
                }
            }
        }
        if(temp){
            count++;
            ax[temp]=300,ay[temp]=300;
        }
    }
    printf("%d\n",count);
    return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.io.*;
class Main{
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int arr[]=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=in.nextInt();
		}
		dp=new long[n+1][n+1];
		for(int i=0;i<dp.length;i++) {
			Arrays.fill(dp[i], -1);
		}
		System.out.println(call(0,n-1,arr));
		
	}

	static long dp[][];
	static long call(int i,int j,int arr[]) {
		if(i>=j)return 0;
		if(dp[i][j]!=-1)return dp[i][j];
		long ans=Long.MAX_VALUE;
		for(int k=i;k<j;k++) {
			ans=Math.min(ans, call(i,k,arr)+sum(i,k,arr)+sum(k+1,j,arr)+call(k+1,j,arr));
		}
		return dp[i][j]=ans;
	}
	static long sum(int i,int j,int arr[]) {
		long ans=0;
		for(int k=i;k<=j;k++) {
			ans+=arr[k];
	
		}
return ans;	
}
	
}


Measured memory_bytes: 25772
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

int main(){
    long long N,A,B;
    cin >> N >> A >> B;
    long long div = N / (A+B);
    long long p = N % (A+B);
    if(p < A) cout << div*A+p << endl;
    else cout << div*A+A << endl;
}

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


int main()
{
ll h,n,sum=0,i,j;
cin>>h>>n;
ll arr[n];
for(i=0;i<n;i++)
{
  cin>>arr[i];
  sum+=arr[i];
}
if(sum<h)cout<<"No"<<"\n";
else cout<<"Yes"<<"\n";



return 0;

}

Measured memory_bytes: 1024
n = int(input())
l = list(map(int,input().split()))

m = 0
a_sum = sum(l[:1])
b_sum = sum(l[1:])
m=abs(a_sum - b_sum)

for i in range(n)[1:]:
  a = l[:i]
  b = l[i:]
  a_sum = sum(a)
  b_sum = sum(b)
  mi=abs(a_sum - b_sum)
  m=min(m,mi)
  
print(m)

Measured memory_bytes: 3064
N=int(input())
p=list(map(int,input().split()))
ANS=0
ans=p[0]-p[1]
for i in range(2,N):
    if (p[i-1]-p[i])*ans>=0:
        ANS+=1
    ans=(p[i-1]-p[i])//abs(p[i-1]-p[i])
print(ANS)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int qz(double x){
	double z=ceil(x)-x;
	if(z==0.5) return floor(x);
	if(z>0.5) return floor(x);
	if(z<0.5) return ceil(x);
}
int main(){
	int a,b;
	cin>>a>>b;
	double i=1;
	while(true){
		if(i*0.1>=b+1||i*0.08>=a+1){
			cout<<-1;
			return 0;
		}
		double x1,x2;
		x1=i*0.08;
		x2=i*0.1;
		if(floor(x1)==a&&floor(x2)==b){
			cout<<i;
			return 0;
		}
		/* 
		if(qz(x1)==a&&qz(x2)==b){
			cout<<i;
			return 0;
		}
		*/ 
		i+=1;
	}
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
import math
from heapq import heappush, heappop, heapify

def solve(s):
  n = len(s)
  k = n
  for i in range(n-1):
    if s[i] != s[i+1]:
      k = min(k, max(i+1, n-i-1))
  return k

def main():
  s = input()
  ans = solve(s)
  print(ans)
  

if __name__=='__main__':
  main()

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct edge{
    int to,cap,cost,rev;
    edge(int a,int b,int c,int d):to(a),cap(b),cost(c),rev(d){}
};
const int MAX_V=6010;
const int INF=1001001001;
vector<edge>G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
bool used[MAX_V];
int prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost){
    G[from].push_back(edge(to,cap,cost,G[to].size()));
    G[to].push_back(edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int s,int t,int f){
    vint deg(MAX_V);
    rep(i,MAX_V)for(auto &e:G[i])if(e.cap)deg[e.to]++;

    fill_n(h,MAX_V,INF*2);
    queue<int>que;
    rep(i,MAX_V)if(deg[i]==0){
        if(i==s)h[i]=0;
        que.push(i);
    }
    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto &e:G[v])if(e.cap){
            chmin(h[e.to],h[v]+e.cost);
            if(--deg[e.to]==0)que.push(e.to);
        }
    }

    int res=0;
    while(f>0){
        fill_n(dist,MAX_V,INF);
        dist[s]=0;
        memset(used,0,sizeof(used));
        while(true){
            int v=-1;
            for(int u=0;u<MAX_V;u++)if(!used[u]&&(v==-1||dist[v]>dist[u]))v=u;
            if(v==-1)break;
            used[v]=true;
            if(dist[v]==INF)break;
            for(int i=0;i<G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap==0||dist[e.to]<=dist[v]+e.cost+h[v]-h[e.to])continue;
                dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                prevv[e.to]=v;
                preve[e.to]=i;
            }
        }
        if(dist[t]==INF)return -1;
        int d=f;
        for(int v=t;v!=s;v=prevv[v]){
            d=min(d,G[prevv[v]][preve[v]].cap);
        }
        for(int v=0;v<MAX_V;v++)h[v]+=dist[v];

        f-=d;
        res+=d*h[t];
        for(int v=t;v!=s;v=prevv[v]){
            edge &e=G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}



signed main(){
    int n,v,xl,xr;

    cin>>n>>v>>xl>>xr;
    vint x(n),t(n),p(n);

    rep(i,n){
        cin>>x[i]>>t[i]>>p[i];
    }
    int src=MAX_V-2,snk=MAX_V-1,l=MAX_V-3,r=MAX_V-4;

    rep(i,n){
        add_edge(i*2,i*2+1,1,-p[i]);
        add_edge(i*2+1,snk,1,0);

        if(abs(xl-x[i])<=t[i]*v)add_edge(l,i*2,1,0);
        if(abs(xr-x[i])<=t[i]*v)add_edge(r,i*2,1,0);
    }

    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j){
        if(abs(x[i]-x[j])<=v*(t[j]-t[i])){
            add_edge(i*2+1,j*2,1,0);
        }
    }
    add_edge(src,snk,2,0);
    add_edge(src,l,1,0);
    add_edge(src,r,1,0);

    cout<<-min_cost_flow(src,snk,2)<<endl;
    return 0;
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int3(n, a, b);

    cout << min(n * a, b) << endl;

    return 0;
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long a, long long b, long long c, long long d, long long e, long long k){
    string result = (e - a > k ? ":(" : "Yay!");
    cout << result << endl;
}

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long c;
    scanf("%lld",&c);
    long long d;
    scanf("%lld",&d);
    long long e;
    scanf("%lld",&e);
    long long k;
    scanf("%lld",&k);
    solve(a, b, c, d, e, k);
    return 0;
}


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

using namespace std;
const int MOD = 1000000007,MAX = 510000;
long int pow107 = (int)pow(10, 9) + 7,llimit = LONG_MAX,fac[MAX], finv[MAX], inv[MAX];
int ilimit = INT_MAX;

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long int COM(long int n,long int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

bool comp(pair<int, int> a, pair<int, int> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % pow107;
    }
    return f;
}

bool pn(long int x){
    if(x != 2 && x % 2 == 0)
        return false;
    for(int i = 3; i < x; ++i){
        if(x != i && x % i == 0)
            return false;
    }
    return true;
}

long int factorial(long int n){
    long int f = 1;
    for(long int i = 1; i <= n; ++i){
        f = f * i % pow107;
    }
    return f;
}

long int Func2(long int n,long int m){
    long int s2 = 1,
        r = 1;
    for(long int i = 1; i <= m; ++i){
        s2 = (s2*(n - (i - 1))/i) % (pow107);
    }
    return s2;
}

bool secsort(pair<int, int> a, pair<int, int> b){
    if(a.second == b.second)return a.first > b.first;
    else return a.second > b.second;
}

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

long int LCM(long int a,long int b){
    return a/GCD(a,b)*b;
}

//long intの最大llimit
//intの最大ilimit
//10^9+7    pow107
//素数pn
//n乗jou
//階乗factorial
//コンビネーションFunc2
//コンビネーションCOMinit(),COM(n,m)

int main(){
    char a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a == b && b == c || b == c && c == d){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (ll r = a % b)
		a = b, b = r;
	return b;
}

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

	ll modinv(ll a)
	{
		ll b = max, u = 1, v = 0;
		while (b)
		{
			ll t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= max;
		if (u < 0)
			u += max;
		return u;
	}

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

//	for priority queue
//	priority_queue<ipair, vector<ipair>, greater<ipair>>
using ipair = pair<int, pair<int, int>>;
bool operator>(const ipair a, const ipair b) { return a.first > b.first; };
bool operator<(const ipair a, const ipair b) { return a.first < b.first; };

using xpair = pair<int, int>;
bool operator>(const xpair &a, const xpair &b) { return a.second > b.second || (a.second == b.second && a.first > b.first); };
bool operator<(const xpair &a, const xpair &b) { return a.second < b.second || (a.second == b.second && a.first > b.first); };
bool operator==(const xpair &a, const xpair &b) { return a.first== b.first; };

int main()
{
	struct node { int x, y, p; };

	int h, w, white = 0;
	cin >> h >> w;
	vector<vector<bool>> s(h, vector<bool>(w, false));
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
		{
			char c;
			cin >> c;
			s[i][j] = c == '.';
			if (s[i][j])
				white++;
		}
	vector<vector<int>> v(h, vector<int>(w, 1e8));
	v[0][0] = 0;
	
	queue<node> k;
	k.push({ 0,0,1 });

	while (!k.empty())
	{
		int y = k.front().y;
		int x = k.front().x;
		int p = k.front().p;
		p++;
		k.pop();
		if (x < w - 1 && s[y][x + 1] && v[y][x + 1] > p)
		{
			k.push({ x + 1, y, p });
			v[y][x + 1] = p;
		}
		if (x > 0 && s[y][x - 1] && v[y][x - 1] > p)
		{
			k.push({ x - 1, y, p });
			v[y][x - 1] = p;
		}
		if (y < h - 1 && s[y + 1][x] && v[y + 1][x] > p)
		{
			k.push({ x, y + 1, p });
			v[y + 1][x] = p;
		}
		if (y > 0 && s[y - 1][x] && v[y - 1][x] > p)
		{
			k.push({ x, y - 1, p });
			v[y - 1][x] = p;
		}
		if (x == w - 2 && y == h - 1 || x == w - 1 && y == h - 2)
			break;
	}

	if (v[h - 1][w - 1] == 1e8)
		printf("-1");
	else
		printf("%d", white - v[h - 1][w - 1]);

	return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<iostream>
#include<algorithm>//next_permutation
#include<complex>
#include<math.h>
#include<sstream>
#include<stdio.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rep2(i, j, n) for (int i = j; i < (int)(n); i++)
using ll = long long int;
int main() {
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	if (k <= a) {
		cout << k << endl;
	}
	else if(k <= a + b){
		cout << a << endl;
	}
	else {
		cout << a - k + a + b << endl;
	}
}


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

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = int.Parse(Console.ReadLine());

            var l = new List<int>();
            l.Add(s);

            while(true){
                var x = l.Last();
                var y = x % 2 == 0 ? x / 2 : x * 3 + 1;

                if(l.IndexOf(y) != -1){
                    Console.WriteLine(l.Count() + 1);
                    break;
                }
                l.Add(y);
            }
        }
    }
}


Measured memory_bytes: 13268
import math
n = int(input())
lis = [0 for i in range(n)]
for i in range(2,n+1):
  cou = 2
  while i >= cou:
    if i % cou == 0:
      lis[cou-1] += 1
      i //= cou
    else:
      cou += 1
cou = 1
for i in range(len(lis)):
  cou *= (lis[i]+1)
  cou %= (10 ** 9+7)
print(cou)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  LL k,a,b,d,e;
  
  cin>>k;
  cin>>a>>b;
  if(a%k!=0)
    d= a/k +1;
  else
    d = a/k;
  if(a%k!=0)
    e=b/k +1;
  else
    e = b/k;
  if(k==1){
    if(a>=k || b>=k)
  		cout<<"OK";
  }
  else if(d*k>=a && d*k<=b || e*k>=a && e*k<=b){
    	cout<<"OK";
   }
   else{
    	cout<<"NG";
  	}
   

  
return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int main(){
	int n; cin >> n;
	
	int ans = 0;
	for(int i = 1; i <= n; i += 2) {
		int count = 0;
		
		for(int j = 1; j <= n; j++) {
			if(i % j) continue;
			count += 1;
		}
		
		ans += (count == 8);
	}
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
#define PI acos(-1.0)
#define eps 1e-9
#define ll long long
#define ull unsigned long long
#define nl printf("\n")
#define sf scanf
#define pf printf
#define INF (ll)1e15
#define mod 1000000007

///#define isValid(n,m,nx,ny)nx>=0&&nx<n&&ny>=0&&ny<m
///int kx[]={1, 1, -1, -1, 2, 2, -2, -2}; //knight moves
///int ky[]={2,-2,  2, -2, 1,-1,  1, -1}; //knight moves
///int dx[]={1,-1,0,0,1,-1,1,-1};//eight direction
///int dy[]={0,0,1,-1,1,-1,-1,1};//eight direction
 
///using namespace __gnu_pbds;
using namespace std;
 
///inline double toRad(double deg){return deg*PI/180;}
///inline double toDeg(double rad){return rad*180/PI;}
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;
 
const int S=123456;
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    #endif
    ll a,b,c,x,y;
    while(sf("%lld %lld %lld %lld %lld",&a,&b,&c,&x,&y)==5)
    {
        ll ab=(a*x+b*y);

        ll mn=min(x,y);
        ll mx=max(x,y);
        x-=mn;
        y-=mn;
        ll both=mn*c*2;
        if(x!=0)
        {
            if(2*c<a)both+=(x*c*2);
            else both+=(x*a);
        }
        else if(y!=0)
        {
            if(2*c<b)both+=(y*c*2);
            else both+=(y*b);
        }

        ll all=mx*c*2;
        pf("%lld\n",min({ab,both,all}));
    }
    return 0;
}
 









 




























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

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

  for (int i = s.size() - 2; i >= 0; i--) {
    string ss = s.substr(0, i);
    // cout << s << ":" << ss << endl;
    if (ss.size() % 2 != 0) {
      continue;
    }
    if (ss.size() < 2) {
      break;
    }
    bool flag = true;
    for (int j = 0; j < ss.size() / 2; j++) {
      if (ss[j] != ss[j + (ss.size() / 2)]) {
        flag = false;
        break;
      }
    }
    if (flag) {
      cout << ss.size() << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
N=int(input())
h=list(map(int,input().split()))
INF=10**9
dp=[INF]*(N)#dp[i] 足場i+1にいるときの最小コスト
dp[0]=0
for i in range(N+1):
    if i+2<=N-1:
        dp[i+2]=min(dp[i]+abs(h[i]-h[i+2]),dp[i+2])
    if i+1<=N-1:
        dp[i+1]=min(dp[i]+abs(h[i]-h[i+1]),dp[i+1])
print(dp[N-1])


Measured memory_bytes: 52208
#include <iostream>
	#include <cstdio>
	#include <algorithm>
	#include <string>
	#include <cstring>
	#include <cctype>
	#include <cmath>
	#include <stack>
	#include <queue>
	#include <vector>
	#include <set>
	#include <map>
	#include <list>
	#include <stdio.h>
	#include <string.h>
	#include <cstdlib>
	#include <math.h>
	#include <bitset>
	#include <iterator>
	#include <iomanip>
	#include <sstream>
	#include <numeric>
	#include <cassert>
	using namespace std;
	int dx[5]={1,0,-1,0,0},dy[5]={0,1,0,-1,0};
	long long gcd(long long a,long long b){if(a%b==0){return b;}else return gcd(b,a%b);}
	long long lcm(long long a,long long b){if(a==0){return b;} return a/gcd(a,b)*b;}
	#define INF 2000000000
	#define MOD 1000000007
	#define sym cout<<"---------"<<endl;
	#define ll long long
	#define mk make_pair
	#define en endl
	#define RE return 0
	#define int ll
	#define P pair<int,int>

	int n,m; 
	void solve(int m){
		int ans=-1;
		for(int i=1; i*i<=m; i++){
			if(m%i==0){
				if(i*n<=m) ans=max(ans,i);
				if((m/i)*n<=m) ans=max(ans,m/i);
			}
		}
		cout<<ans<<en;
	}

	signed main(){
		cin>>n>>m;
		solve(m);
	}




Measured memory_bytes: 256
S = input()
N = len(S)

children = [0] * N

turn_position = list()

for i in range(N-1):
	if S[i]=='R' and S[i+1]=='L':
		turn_position.append(i)

for turn_i in range(len(turn_position) - 1):
	turn_pos = turn_position[turn_i]
	turn_pos_next = turn_position[turn_i + 1]

	children[turn_pos] += 1
	children[turn_pos+1] += 1

	for pos_i in range(turn_pos+2, turn_pos_next):
		if S[pos_i] == 'L':
			if (pos_i - turn_pos) % 2 == 0:
				children[turn_pos] += 1
			else:
				children[turn_pos+1] += 1
		else:
			if (turn_pos_next - pos_i) % 2 == 0:
				children[turn_pos_next] += 1
			else:
				children[turn_pos_next+1] += 1

turn_pos_first = turn_position[0]
for pos_i in range(0, turn_pos_first):
	if (turn_pos_first - pos_i) % 2 == 0:
		children[turn_pos_first] += 1
	else:
		children[turn_pos_first+1] += 1

turn_pos_last = turn_position[-1]
children[turn_pos_last] += 1
children[turn_pos_last+1] += 1
for pos_i in range(turn_pos_last+2, N):
	if (pos_i - turn_pos_last) % 2 == 0:
		children[turn_pos_last] += 1
	else:
		children[turn_pos_last+1] += 1

print(*children)


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

#define faster  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define sq(x)   (x)*(x)
#define PI      acos(-1.0)
#define all(x) x.begin(),x.end()
#define nl      '\n'

typedef long long int ll;
typedef unsigned long long int  llu;

int main()
{
    int n;
    cin >> n;
    ll dp[n + 1] = {};
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= n; j += i)
        {
            dp[j]++;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += dp[i] * i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 81700
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    int n;
    List<bool[]> map = new List<bool[]>();
    void Run()
    {
        var scn = new Scanner();
        n = scn.NextInt();
        string s = scn.NextString();
        Dfs(0, new bool[n]);

        string l = s.Substring(0, n);
        string r = Reverse(s.Substring(n, n));

        var left = new Dictionary<string, Dictionary<string, long>>();
        var right = new Dictionary<string, Dictionary<string, long>>();

        for (int k = 0; k < map.Count; k++)
        {
            var sa = new StringBuilder();
            var sb = new StringBuilder();
            var sc = new StringBuilder();
            var sd = new StringBuilder();
            for (int i = 0; i < map[k].Length; i++)
            {
                (map[k][i] ? sa : sb).Append(l[i]);
                (map[k][i] ? sc : sd).Append(r[i]);
            }
            string a = sa.ToString();
            string b = sb.ToString();
            string c = sc.ToString();
            string d = sd.ToString();
            if (!left.ContainsKey(a)) left.Add(a, new Dictionary<string, long>());
            if (!left[a].ContainsKey(b)) left[a].Add(b, 0);
            left[a][b]++;
            if (!right.ContainsKey(c)) right.Add(c, new Dictionary<string, long>());
            if (!right[c].ContainsKey(d)) right[c].Add(d, 0);
            right[c][d]++;
        }
        long ans = 0;
        foreach (string k in left.Keys)
        {
            if (!right.ContainsKey(k)) continue;
            foreach (string j in left[k].Keys)
                if (right[k].ContainsKey(j)) ans += left[k][j] * right[k][j];
        }
        Console.WriteLine(ans);
    }

    void Dfs(int i, bool[] arr)
    {
        if (i == n)
        {
            bool[] res = new bool[n];
            Array.Copy(arr, res, n);
            map.Add(res);
            return;
        }
        arr[i] = true;
        Dfs(i + 1, arr);
        arr[i] = false;
        Dfs(i + 1, arr);
    }

    string Reverse(string s)
    {
        var c = s.ToCharArray();
        Array.Reverse(c);
        return new string(c);
    }

    static long Gcd(long a, long b)
    {
        if (a < b) return Gcd(b, a);
        if (b == 0) return a;
        return Gcd(b, a % b);
    }

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

class Scanner
{
    int index = -1;
    string[] buf;

    public Scanner()
    {
    }

    public int NextInt()
    {
        CheckNext();
        return int.Parse(buf[index++]);
    }

    public long NextLong()
    {
        CheckNext();
        return long.Parse(buf[index++]);
    }

    public double NextDouble()
    {
        CheckNext();
        return double.Parse(buf[index++]);
    }

    public string NextString()
    {
        CheckNext();
        return buf[index++];
    }

    private void CheckNext()
    {
        if (index >= 0 && index < buf.Length) return;

        buf = Console.ReadLine().Split(' ');
        index = 0;
    }
}


Measured memory_bytes: 203024
#include<iostream>
#include<string>
#include<vector>
#include<climits>
#include<queue>
#define ll long long int
#define oo 1000000000000000000
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define pb push_back

using namespace std;

const ll MOD = 1e9 + 7;

ll f[1000100];

pair<int,int> dxy[4] = {{1,0} , {-1,0} , {0,1} , {0,-1}};

void __sol(){
    int n,m,k; cin >> n >> m >> k;
    int x,y,go,to; cin >> x >> y >> go >> to;
    vector<string> v(n+3);
    forr(i,n) cin >> v[i+1] , v[i+1] = '@'+v[i+1]+'@';
    string faltu(m+3,'@');
    v[0] = faltu;
    v[n+1] = faltu;

 //   x-- , y-- , go--,to--;
    int d[n+1][m+1];
    //memset(d,-1,sizeof(d));
    forr(i,n+1) forr(j,m+1) d[i][j]=n*m;
    d[x][y]=0;
    queue<pair<int,int>> qq; qq.push({x,y});
    while(!qq.empty()){
        pair<int,int> p = qq.front(); qq.pop();
        x = p.first ,y= p.second; //cout << x <<" " << y << "\n"; 
        if(x==go && y==to){
            cout << d[go][to];
            return;
        }
        for(auto &ooo: dxy){
            int p = ooo.first , q = ooo.second;
            for(int i=1;i<=k;i++){
             //   if( x+i*p<n && x+i*p>=0 && y+i*q<m && y+i*q>=0){
                    if( v[x+i*p][y+i*q]!='.' || d[x+i*p][y+i*q]<=d[x][y] ) break;
                    if(d[x+i*p][y+i*q] > 1 + d[x][y]){
                        d[x+i*p][y+i*q] = 1 + d[x][y];
                        qq.push({x+i*p , y+i*q});
                    }
            }
        }
    }
    if(d[go][to]!=n*m) cout << d[go][to];
    else cout << -1;
}


int main(){
    fastio
    ll tc=1;// cin >> tc;
    while(tc--) __sol();
    return 0;
}


Measured memory_bytes: 14952
#include <bits/stdc++.h>
using namespace std;
using f32 = float;
using f64 = double;
using LL = long long;
using ULL = unsigned long long;
#define REP(i, n) for (LL i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (LL i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
const long long MOD = 998244353;
int main(){
    long long N,S;
    scanf("%lld",&N);
    scanf("%lld",&S);
    vector<long long> A(N);
    REP(i,N)scanf("%lld",&A[i]);
    vector<vector<long long>> dp(N+1, vector<long long>(S+1, 0));
    dp[0][0] = 1;
    REP(i,N){
        REP(j,S+1){
          dp[i + 1][j] += 2 * dp[i][j];
             dp[i + 1][j] %= MOD;
           if (j + A[i] <= S) dp[i + 1][j + A[i]] += dp[i][j];
           dp[i + 1][j + A[i]] %= MOD;
        }
    }
    printf("%lld",dp[N][S]);
    return 0;
}

Measured memory_bytes: 73740
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		ArrayList<String> strList = new ArrayList<String>();

		for(int i = 0; i < N; i++) {
			strList.add(sc.next());
		}

		List<String> listB = new ArrayList<String>(new HashSet<>(strList));

		System.out.println(listB.size());
	}
}


Measured memory_bytes: 78572
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!$BDs=P;~$K%3%a%s%H%"%&%H(B!!
#ifdef DEBUG_
#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

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

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

    template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int mod = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};


signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    int N; cin >> N;
    VL A(N);
    REP(i,N) cin >> A[i];

    LL ans = A[0]-1;
    A[0] = 1;
    LL pre = 1;
    FOR(i,1,N){

        if(A[i] == pre+1){
            pre++;
            continue;
        }

        if(A[i] % (pre+1) == 0){
            A[i] -= pre+2;
            ans++;
            ans += A[i] / (pre+1);
            A[i] %= pre+1;
        }else{
            ans += A[i] / (pre+1);
            A[i] %= pre+1;
        }

    }

    //REP(i,N){
    //    cout << A[i] << " ";
    //}
    //cout << endl;

    cout << ans << endl;

}

Measured memory_bytes: 3964
# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: list(map(int, raw_input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

h, N = gets()
AB = getss(N)

dp = [0] + [float('inf')] * h
for a, b in AB:
    for i in range(h):
        j = min(i + a, h)
        dp[j] = min(dp[j], dp[i] + b)
print(dp[h])


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

#ifndef errOut
#define errOut(s)
#endif

std::string nextDiverseWord(const std::string& s) {
    if (s == "zyxwvutsrqponmlkjihgfedcba") {
        return "-1";
    }

    std::array<bool, 26> exists {};
    if (s.length() < 26) {
        for (auto ch: s) {
            exists[ch - 'a'] = true;
        }
        for (int i = 0; i < 26; i++) {
            if (exists[i]) {
                continue;
            }
            return s + static_cast<char>('a' + i);
        }
        return "-1";
    }

    std::string ret = s;
    for (int r = 25; r >= 0; --r) {
        char ch = ret[r];
        for (int i = ch - 'a' + 1; i < 26; i++) {
            if (!exists[i]) {
                continue;
            }
            ret[r] = static_cast<char>('a' + i);
            return ret;
        }
        exists[ch - 'a'] = true;
        ret = ret.substr(0, (size_t)r);
    }
    return "-1";
}

int main() {
    std::string s;
    std::cin >> s;
    std::cout << nextDiverseWord(s) << std::endl;
    return 0;
}

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

int dp[1005][10005];

struct magic{
    int d,c;
};

int main(){
    int h,n;
    cin >> h >> n;
    // vector<vector<int>> dp(n,vector<int>(h+1,INF));
    vector<magic> ms(n);
    rep(i,n){
        int a, b; cin >> a >> b;
        // ms[i].d = a;ms[i].c = b;
        magic p; p.d = a;p.c = b;
        ms[i] = p;
    }
    
    rep(i,n+1)dp[i][0]=0;
    rep(i,h+1)dp[0][i]=INF;
    rep(i,n){
        rrep(j,h){
            if(j-ms[i].d <0){
                dp[i+1][j] = min(dp[i][j],dp[i+1][0]+ms[i].c);
            }
            else dp[i+1][j] = min(dp[i][j],dp[i+1][j-ms[i].d]+ms[i].c);
        }
    }
    // rep(i,n+1){
    //     rep(j,h+1){
    //         cout<<dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

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

Measured memory_bytes: 39424
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

class union_find{
  int n_; 
  vector<int> par, rank, size;
public:
  union_find(int n): n_{n} {
    par.resize(n_);
    rank.resize(n_);
    size.resize(n_);

    REP(i, n_){
      par[i] = i;
      rank[i] = 1;
      size[i] = 1;
    }
  } 

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;

    if(rank[x] > rank[y]){
      par[y] = x;
      size[x] += size[y];
    } else {
      par[x] = y;
      size[y] += size[x];
      if(rank[x] == rank[y]) rank[y]++;
    }
  }

  int find(int x) {
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
  }
};

struct edge {
    int s, t, w;

    bool operator< (const edge& other) const {
        if (w != other.w) {
            return w < other.w;
        } else if (s != other.s) {
            return s < other.s;
        } else {
            return t < other.t;
        }
    }
};

pair<int, vector<bool>> kruskal(int n, const vector<edge>& e, int del = -1) {
    union_find uf(n);
    vector<bool> used(e.size(), false);

    int ret = 0;
    REP(i, e.size()) {
        if (i == del) continue;
        if (!uf.same(e[i].s, e[i].t)) {
            ret += e[i].w;
            uf.unite(e[i].s, e[i].t);
            used[i] = true;
        }
    }

    return {ret, used};
}

int main() {
    int n, m; cin >> n >> m;
    vector<edge> e(m);

    REP(i, m) {
        int s, d, c; cin >> s >> d >> c;
        --s; --d;
        e[i] = {s, d, c};
    }

    sort(e.begin(), e.end());

    auto ret = kruskal(n, e);
    const int cost = ret.first;
    const vector<bool> used = ret.second;
    
    int cnt = 0, w = 0;
    REP(i, m) {
        if (!used[i]) continue;
        if (cost != kruskal(n, e, i).first) {
            cnt++; 
            w += e[i].w;
        }
    }

    cout << cnt << " " << w << endl;
    
    return 0;
}



Measured memory_bytes: 3368
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
static const double pi = 3.14159265359;

int n;
struct Point { double x, y; };
//線分を三分して三角形に
void koch(Point p1 ,Point p2,int i ) {
	if (i == n) {
		return;
	}
	Point s, t, u;
	s.x = (2 * p1.x + p2.x) / 3;
	s.y = (2 * p1.y + p2.y) / 3;
	t.x = (p1.x + 2 * p2.x) / 3;
	t.y = (p1.y + 2 * p2.y) / 3;
	u.x = (t.x - s.x) * cos(pi / 3) - (t.y - s.y) * sin(pi / 3) + s.x;
	u.y = (t.x - s.x) * sin(pi / 3) + (t.y - s.y) * cos(pi / 3) + s.y;
	koch(p1, s, i + 1);
	printf("%.8f %.8f\n", s.x, s.y);
	koch(s, u, i + 1);
	printf("%.8f %.8f\n", u.x, u.y);
	koch(u, t, i + 1);
	printf("%.8f %.8f\n", t.x, t.y);
	koch(t, p2, i + 1);
	
}

//二分探索
int main() {
	cin >> n;
	Point p1, p2;
	p1.x = 0;
	p1.y = 0;
	p2.x = 100;
	p2.y = 0;
	printf("%.8f %.8f\n", p1.x, p1.y);
	koch(p1, p2, 0);
	printf("%.8f %.8f\n", p2.x, p2.y);

}


Measured memory_bytes: 3228