akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
 
int main(){
    ll A, B;
    cin >> A >> B;
    ll res = A*B - (1*A+1*B-1*1);
    cout << res << "\n";
}


Measured memory_bytes: 256
import java.util.*;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;


public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n==3 || n==5 || n==7) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
        
    }
}


Measured memory_bytes: 23124
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define INF 10000000
 
 
int scalar(int *);
int min(int,int);
 
int p[MAX];
int m[MAX][MAX];
int n;
 
int main(){
  int i;
   
  scanf("%d",&n);
   
  for(i=0 ; i<n ;i++){
    scanf("%d%d",&p[i],&p[i+1]);
  }
 
  printf("%d\n",scalar(p));
   
  return 0;
}
 
int scalar(int *p){
  int i,j,k,l,q;
  for(i=1 ; i<=n ; i++){
    m[i][i]=0;
  }
 
  for(l=2 ; l<=n ; l++){
    for(i=1 ; i<=n-l+1 ; i++){
      j=i+l-1;
      m[i][j]=INF;
      for(k=i ; k<j ; k++){
    q = m[i][k] + m[k+1][j] + p[i-1]* p[k] * p[j];
    m[i][j]=min(m[i][j],q);
      }     
    }
  }
  return m[1][j];
}
 
int min(int m,int q){
  if(m<q)return m;
  else return q;
}

Measured memory_bytes: 636
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut ws = vec![0; n];
    for i in 0..n {
        ws[i] = read::<i64>();
    }
    let mut ans = 1 << 30;
    for i in 1..n {
        let s1: i64 = ws[..i].iter().sum();
        let s2: i64 = ws[i..].iter().sum();
        ans = std::cmp::min(ans, (s1 - s2).abs());
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

vector<ll> Factorial(ll M, ll MOD){
    vector<ll> result = vector<ll>(M + 1);
    for(int i = 0; i <= M; i++){
        if(i == 0){
            result[i] = 1;
        }else{
            result[i] = result[i-1] * i % MOD;
        }
    }
    return result;
}

vector<ll> InvFact(ll M, ll MOD){
    vector<ll> result = vector<ll>(M + 1);
    vector<ll> inv = vector<ll> (M + 1);
    result[0] = 1;
    result[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < M; i++){
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        result[i] = result[i - 1] * inv[i] % MOD;
    }
    return result;
}

ll Combination(ll n,ll k,vector<ll>& fact, vector<ll>& invFact,ll MOD){
    //nCkを計算する
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fact[n] * (invFact[k] * invFact[n - k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    ll n,a,b;
    cin >> n >> a >> b;
    ll MOD = 1000000007;
    ll sum = modpow(2,n,MOD);
    //cout << sum << endl;
    ll A = 1;
    ll B = 1;
    auto invFact = InvFact(300000,MOD);
    for (int i = 0; i < a; ++i) {
        A = A * (n - i) % MOD;
    }
    A = A * invFact[a] % MOD;
    for (int i = 0; i < b; ++i) {
        B =  B * (n - i) % MOD;
    }
    B = B * invFact[b] % MOD;
    sum = (sum - A + MOD) % MOD;
    sum = (sum - B + MOD) % MOD;
    sum = (sum - 1 + MOD) % MOD;
    //cout << A << "," << B << endl;
    cout << sum << endl;

}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
2 2 3
2 2 2 3 3 3
2 2 2 2 3 5
4 6 10でとりたい

どうしよう
ユニークもっかい？
2222 3333 5
222333 235
4通りとれる
222222 3333 5
22222 333 235 =5

22333
23 233

2222 3 55
2225 235

22222 3 55

22222222

22 222 222=2

複数同士のペアがだめ

同じ数字のペアじゃないとだめなのか勘違い

22222
*/
int main(){
  ll N,ans=0; cin>>N;
  ll n=N, cnt=2;
  map<ll,ll> M;
  while(n/cnt>=cnt){
    if(n%cnt==0){
      n/=cnt;
      M[cnt]++;
      cnt--;
    }
    cnt++;
  }
  if(n>1) M[n]++;
  for(auto v:M){
    ll v1=v.first;
    ll v2=v.second;
    cnt=1;
//cout<<"v1:"<<v1<<" v2:"<<v2<<endl;
    while(v2-cnt>=0){
      v2-=cnt;
      ans++;
      cnt++;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <set>
using namespace std;
int main(){
  int N,A;
  set<int> Aset;
  bool used=false;
  for(cin >> N;N>0;N--){
    cin >> A;
    if(Aset.end()!=Aset.find(A))used=true;
    Aset.insert(A);
  }
  cout << (!used?"YES":"NO") << endl;
  return 0;
}

Measured memory_bytes: 9600
# https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_b
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(text: str):
    print(text)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


from collections import Counter
N = a_int()
D = ints()
M = a_int()
T = ints()

cnt = Counter(D)
for t in T:
    cnt[t] -= 1
    if cnt[t] < 0:
        exit('NO')

print('YES')


Measured memory_bytes: 133076
#include<stdio.h>
int main(void)
{
  int n,i,j;
  scanf("%d",&n);
  int A[n];
  for(i=0;i<n;i++) scanf("%d",&A[i]);
  int x=A[n-1],flag=-1,tmp;
  for(j=0;j<n-1;j++)
  {
    if(A[j]<=x)
    {
      flag=flag+1;
      tmp=A[flag];
      A[flag]=A[j];
      A[j]=tmp;
    }
  }
  tmp=A[flag+1];
  A[flag+1]=A[n-1];
  A[n-1]=tmp;

  for(i=0;i<n;i++)
  {
    if(i==flag+1) printf("[%d] ",A[i]);
    else if(i==n-1) printf("%d",A[i]);
    else printf("%d ",A[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 2200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int n;
ll a[11000];
ll b[11000];
int main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];
    ll A=0,B=0;
    rep(i,n){
        ll need=b[i]-a[i];
        if(need>=0){
            need=(need+1)/2;
            A+=need;
            B+=(a[i]+need*2)-b[i];
        }
        else{
            B+=a[i]-b[i];
        }
    }
    //cout<<A<<" "<<B<<endl;
    if(A==B){
        cout<<"Yes"<<endl;
    }
    else{
        if(B>A){
            cout<<"No"<<endl;
        }
        else if(A>B){
            cout<<"Yes"<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 384
/*input
8 6
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}
string s[]={"Even","Odd"};
int main()
{
	IOS;
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<min(a,b)+min(c,d);
	return 0;
}


Measured memory_bytes: 256
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

a,b,c = Is()
print(min(b//a,c))

Measured memory_bytes: 3436
#include<stdio.h>
int main(void)
{
    int n,a[100],i;
    double s=0.0,ans;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        s+=1.0/(double)a[i];
    }
    ans=1.0/s;
    printf("%lf\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))

int main(){
    int N;
    cin >> N;
    int k = -1;
    for(int i = 1; i < 1000; i++){
        if(i * (i - 1) / 2 == N){
            k = i;
            break;
        }
    }
    if(k == -1){
        cout << "No" << endl;
        return 0;
    }
    vector<int> ans[k];
    int count = 0;
    for(int i = 0; i < k; i++){
        for(int j = i + 1; j < k; j++){
            count++;
            ans[i].push_back(count);
            ans[j].push_back(count);
        }
    }
    cout << "Yes" << endl;
    cout << k << endl;
    for(int i = 0; i < k; i++){
        cout << ans[i].size() << " ";
        array_output(all(ans[i]));
    }
}


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

string S;
string AKB = "AKIHABARA";
vector<string> ans;

void rec(string str, int i) {
    if (i == 9) {
        ans.push_back(str);
        return;
    }
    else {
        if (AKB[i] == 'A') {
            rec(str, i+1);
            rec(str+'A', i+1);
        }
        else {
            rec(str+AKB[i], i+1);
        }
    }
    return;
}

int main() {
    cin >> S;

    rec("", 0);

    bool f = false;
    for (int i = 0; i < ans.size(); i++) {
        if (S == ans[i]) {
            f = true;
            break;
        }
    }

    cout << (f ? "YES" : "NO") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INF = 1e18;
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
int main(){
  int n;
  cin>>n;
  int p[n];
  rep(i,n)cin>>p[i];
  int ans =0;
  ll now_min =INF;
  rep(i,n){
    if(p[i]<now_min){
      ans++;
      now_min=p[i];
    }
  }
  cout<<ans<<endl;
}

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

int main()
{
    string s;
    int i = 0, j = 0, x = 0;
    cin >> s;
    for(i = 0; i < s.size(); i++)
    {
        for(j = i + 1; j < s.size(); j++)
        {

        if(s[i] == s[j])
        {
            cout << "no";
            i = -1;
            break;

        }
        }
        if(i == -1)
        {
            x = 1;
            break;
        }
    }

    if(x == 0)
    {
    cout << "yes";
    }



return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  string s[110],t[110];
  
  int n,m;
  cin>>n;
  
  for(int i=0;i<n;i++)
  {
      cin>>s[i];
  }
  cin>>m;
  for(int i=0;i<m;i++)
  {
      cin>>t[i];
  }
  
  int ans=0;
  for(int i=0;i<n;i++)
  {
     int score =0;
       for(int j=0;j<n;j++)
       {
           if(s[i]==s[j])
             score++;
       }
       for(int j=0;j<m;j++)
       {
            if(s[i]==t[j])
              score--;
       }
    
    ans=max(ans,score);
  
  }
  
      cout<<ans<<endl;
}

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

int n, k;
long s, cn, cp, ans;
vector<long> a, r, ds;

vector<long> devisor(long n){
	vector<long> ret;
	for (int i = 1; i*i <= n; ++i){
		if (n % i == 0){
			ret.push_back(i);
			if (i*i != n) ret.push_back(n/i);
		}
	}
	return ret;
}

int main(){
	cin >> n >> k;
	s = 0;
	for (int i = 0; i < n; ++i){
		a.push_back(0);
		cin >> a[i];
		s += a[i];
	}
	r.resize(n);
	ds = devisor(s);
	ans = 1;
	for (auto& d: ds){
		if (d == 1) continue;
		s = 0;
		for (int i = 0; i < n; ++i){
			r[i] = a[i] % d;
			s += r[i];
		}
		sort(r.begin(), r.end());
		cn = 0; cp = d*n - s;
		for (int i = 0; i < n; ++i){
			cn += r[i];
			cp -= d - r[i];
			if (cn == cp && cn <= k){
				if (ans < d) ans = d;
				break;
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 764
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

long long  F[1001];

int P[10010];
void init(int N){
    for(int i=0;i<=N;i++)
        P[i] = i;
}

int root(int a){
    if(P[a]==a)
        return a;
    return(P[a] = root(P[a]));
}

bool is_same_set(int a, int b){
    return root(a) == root(b);
}

void unit(int a, int b){
    P[root(a)] = root(b);
}

int main(){
    F[0] = 1; F[1]=2;
    for(int i=2;i<=1000;i++){
        F[i] = F[i-1]+F[i-2];
        F[i] %= 1001;
    }
    int V,d;
    while(cin >> V >> d){
        int count=0;
        init(V);
        for(int i=1;i<=V;i++){
            for(int j=i+1; j<=V;j++){
                if(abs(F[j]-F[i])<d){
                    unit(i,j);
                }
            }
        }
        for(int i=1;i<=V;i++){
            if(root(i)==i)
                count++;
        }
        cout << count << endl;
    }
}

Measured memory_bytes: 1180
#include<stdio.h>
int main()
{
	int K;
	scanf("%d", &K);
	if (K % 2 == 0)
	{
		printf("%d", K*K / 4);
	}
	else
		printf("%d", (K - 1)*(K + 1) / 4);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define flsh fflush(stdout)
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1000000000007
 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;


void solve()
{
    ll n;
    cin>>n;
    cout<<(n+1)/2<<"\n";
}


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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 3544
from bisect import bisect_left, bisect_right


n = int(input())
lst_A = sorted(map(int, input().split()))
lst_B = sorted(map(int, input().split()))
lst_C = sorted(map(int, input().split()))


ans = 0
for b in lst_B:
    na = bisect_left(lst_A, b)
    nc = n - bisect_right(lst_C, b)
    ans += na * nc


print(ans)

Measured memory_bytes: 105444
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

// Levenshtein Distance
int levenshtein(string a, string b) {
  int n = a.size(), m = b.size();
  int d[n+1][m+1];
  REP(i, n+1) d[i][0] = i;
  REP(i, m+1) d[0][i] = i;
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      d[i][j] = min(min(d[i-1][j] + 1,  // a deletion
                        d[i][j-1] + 1), // an insertion
                    d[i-1][j-1] + (a[i-1] != b[j-1])); // a substituion
      if (i>=2 && j>=2 && a[i-2]==b[j-1] && a[i-1]==b[j-2])
        d[i][j] = min(d[i][j], d[i-2][j-2]+1);
      //printf("(%d,%d):%d:%d ",i,j,d[i][j],a[i-1]!=b[j-1]);
    }
    //cout << endl;
  }
  return d[n][m];
}

bool judge(string a, string b, int d) {
  if (levenshtein(a,b) <= d) return 1;
  REP(i, a.size()-1) {
    string tmp = a;
    swap(tmp[i], tmp[i+1]);
    //cout << tmp << " " << b << " " << levenshtein(tmp, b) << endl;
    if (levenshtein(tmp, b) <= d-1) return 1;
  }
  REP(i, b.size()-1) {
    string tmp = b;
    swap(tmp[i], tmp[i+1]);
    //cout << tmp << " " << a << " " << levenshtein(tmp, a) << endl;
    if (levenshtein(tmp, a) <= d-1) return 1;
  }
  
  return 0;
}



int main() {
  int n;
  while(cin>>n,n) {
    int d;
    cin >> d;
    string name[n];
    REP(i, n) {
      cin >> name[i];
    }
    set<pair<string, string> > se;
    sort(name, name+n);
    REP(i, n) {
      REP(j, i) {
        //cout << name[j] <<"," <<name[i]<< " :  " << levenshtein(name[j], name[i]) << endl;
        if (judge(name[j], name[i], d))
          se.insert(make_pair(name[j], name[i]));
      }
    }
    FOR(it, se) {
      cout << it->first << "," << it->second << endl;
    }
    cout << se.size() << endl;
  }
}

Measured memory_bytes: 964
// B - Making Triangle
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(int)(s);i<(int)(e);++i)

int main(){
	int N; cin>>N;
	vector<int> L(N); rp(i, 0, N) cin>>L[i];
	sort(L.begin(), L.end());
	int c = 0;
	rp(i, 0, N) rp(j, i+1, N){
		if(L[i] == L[j]) continue;
		rp(k, j+1, N){
			if(L[j] == L[k]) continue;
			if(L[k] == L[i]) continue;
			if(L[i] + L[j] > L[k]) c++;
		}
	}
	cout<< c <<endl;
}


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

#define loop(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)

using namespace std;

template <class T>
using vec = std::vector<T>;
typedef long long ll;
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

const double PI = acos(-1.0);

// long long積のオーバーフロー検出
bool detect_mul_overflow(ll a, ll b)
{
    return a >= LONG_MAX / b;
}

int lcm(int a, int b)
{
    //最小公倍数
    return a / __gcd(a, b) * b;
}

struct edge
{
    int from, to, cost;
};

// int型の2次元配列(3×4要素の)の宣言
// vector<vector<int>> data(3, vector<int>(4));

int N;

int main()
{
    cin>>N;
    vec<ll> A(N+100 ,0);
    rep(i,N){
        cin>>A[i];
    }
    std::sort(A.begin(), A.end(), std::greater<int>());
    ll ans=A[0];
    int index=-1;
    for (int i=0;i<N-2; i++){
        index=i/2+1;
        ans+=A[index];
        // cout<<index<<endl;
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 4832
#include<stdio.h>
int main(void)
{
	int k,x,a,b,c;
	scanf("%d",&k);
	scanf("%d",&x);
	
	a = (x+1) - k;
	b = (x-1) + k;
	
	for(c=a;c<=b;c++){
		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 128
/*
ex4_2
tomatokan
*/
#include<stdio.h>
#include<math.h>

int main(void){
    int hour,minute,hand_hour,hand_minute;
    double angle=0;
    scanf("%d",&hand_hour);
    scanf("%d",&hand_minute);
    scanf("%d",&hour);
    scanf("%d",&minute);
    minute=minute+60*hour;
    angle=minute*11.0*atan(1.0)/90.0;
    printf("%.10f\n",sqrt(hand_hour*hand_hour+hand_minute*hand_minute-2.0*hand_hour*hand_minute*cos(angle)));
    return 0;
}

Measured memory_bytes: 2600
import java.util.*;
import java.io.*;

public class Main {	
	private static void solve(){
		//Implement solution here.
		int N = ni();
		int K = ni();
		int[] p = na(N);
		int cnt = 0;
		double sum = 0;
		double max = 0;
		for(int i = 0; i < N; i++) {
			if(cnt < K) {
				sum += ((double)p[i] + 1) / 2;
				cnt++;
			} else {
				max = Math.max(max, sum);
				sum -= ((double)p[i - K] + 1) / 2;
				sum += ((double)p[i] + 1) / 2;
			}
		}
		max = Math.max(max, sum);
		System.out.println(max);
	}
	
	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}


Measured memory_bytes: 43452
typedef long long int ll;
typedef unsigned long long int ull;
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FOR(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define fore(i, l, r) for (int i = (l); i < (r); ++i)
#define loop for(int i=0;i<n;i++)
#define max3(a,b,c) max(a,max(b,c))
#define max4(a,b,c,d) max3(a,max(b,c),d)
#define max5(a,b,c,d,e) max4(a,max(b,c),d,e)
#define min3(a,b,c) min(a,min(b,c))
#define min4(a,b,c,d) min3(a,min(b,c),d)
#define min5(a,b,c,d,e) min4(a,min(b,c),d,e)
#define sec second
#define fir first
#define vec vector<int>
#define M_PI           3.14159265358979323846  /* pi */
#define pb push_back
#include<bits/stdc++.h>
#include<cmath>
using namespace std;

int main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n;
	cin >> n;
	int v[n + 2], freq[n + 2] = {0};
	FOR(i, n - 1)
	{
		int x;
		cin >> x;
		freq[x]++;
	}
	for (int i = 1; i <= n; i++)
	{
		cout << freq[i] << endl;
	}
}

Measured memory_bytes: 4364
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input=sys.stdin.readline
    n,m=L()
    dic={}
    michi=[1e+7]*(n-1)#部屋2~部屋Nまで→部屋2=michi[0],部屋N→michi[n-2]
    for i in range(m):
        ai,bi=L()
        if ai not in dic:
            dic[ai]=[]
        if bi not in dic:
            dic[bi]=[]
        dic[ai].append(bi)
        dic[bi].append(ai)
    from collections import deque
    d=deque()
    for i in dic[1]:
        michi[i-2]=1
        d.append(i)
    while len(d)!=0:
        i=d.popleft()
        #print(i)
        #tmp=michi[i-2]
        #tmp=i
        for j in dic[i]:
            #print(j,end=' ')
            if j==1:
                continue
            if michi[j-2]==1e+7:
                michi[j-2]=i
                d.append(j)
        #print()
        
    for i in michi:
        if i>=1e+7:
            print('No')
            exit()
    print('Yes')
    for i in michi:
        print(i)
    
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 38484
#include <bits/stdc++.h>
using namespace std;
     
int main() {
  string A, B, C;
  cin >> A >> B >> C;
  
  if(A != "abcb") {
    
  A.push_back('K');
  B.push_back('K');
  C.push_back('K');
  
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  sort(C.begin(), C.end());
  
  char D = 'a';
  
  while(D != 'd'){
  if(D == 'a'){
    
    if(A != "K"){
    
  if(A.at(A.size() - 1) == 'a'){
    D = 'a';
    A.pop_back();
    }
      
  else if(A.at(A.size() - 1) == 'b'){
    D = 'b';
    if(B != "K"){
    B.pop_back();
    }
    else{
      cout << "B" << endl;
      D = 'd';
    }
    }
      
  else if(A.at(A.size() - 1) == 'c'){
    D = 'c';
    if(C != "K"){
    C.pop_back();
    }
    else{
      cout << "C" << endl;
      D = 'd';
    }
    }
  }
    else{
      cout << "A" << endl;
      D = 'd';
    }
  }
    
  ///////
    
  else if(D == 'b'){
    
    if(B != "K"){
    
  if(B.at(B.size() - 1) == 'a'){
    D = 'a';
    if(A != "K"){
    A.pop_back();
    }
    else{
      cout << "A" << endl;
      D = 'd';
    }
    }
      
  else if(B.at(B.size() - 1) == 'b'){
    D = 'b';
    B.pop_back();
    }
      
  else if(B.at(B.size() - 1) == 'c'){
    D = 'c';
    if(C != "K"){
    C.pop_back();
    }
    else{
      cout << "C" << endl;
      D = 'd';
    }
    }
  }
    else{
      cout << "B" << endl;
      D = 'd';
    }
  }
    
  ////////
  
  else if(D == 'c'){
    
    if(C != "K"){
    
  if(C.at(C.size() - 1) == 'a'){
    D = 'a';
    if(A != "K"){
    A.pop_back();
    }
    else{
      cout << "A" << endl;
      D = 'd';
    }
    }
      
  else if(C.at(C.size() - 1) == 'b'){
    D = 'b';
    if(B != "K"){
    B.pop_back();
    }
    else{
      cout << "B" << endl;
      D = 'd';
    }
    }
      
  else if(C.at(C.size() - 1) == 'c'){
    D = 'c';
    C.pop_back();
    }
  }
    else{
      cout << "C" << endl;
      D = 'd';
    }
  }
  }
  }
  
  else{
    cout << "C" << endl;
  }
}

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

using namespace std;
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e10;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;

ll mDiv2(ll n) {
    if (n < 0 && (n % -2 == -1)) {
        return (n / -2) + 1;
    } else {
        return n / -2;
    }
}

ll mMod2(ll n) {
    return abs(n % -2);
}

int main() {

    ll n;
    cin >> n;

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    string ans = "";

    while (n != 0) {
        ll m = mMod2(n);
        n = mDiv2(n);
        ans = ((m == 0) ? '0' : '1') + ans;
    }

    cout << ans << endl;


}


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

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n, m;
    cin >> n >> m;
    int h[n];
    for (int i = 0; i < n; i++)
        cin >> h[i];

    vector<int> connected[n];
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        connected[a - 1].push_back(h[b - 1]);
        connected[b - 1].push_back(h[a - 1]);
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int toAdd = 1;
        for (int x : connected[i])
        {
            if (x >= h[i])
            {
                toAdd = 0;
                break;
            }
        }
        ans += toAdd;
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 9176
#include <stdio.h>
#include <string.h>
int main()
{
	int		N;		/* じゃんけんを行う回数			*/
	int		K;		/* 手の制限回数				*/
	int		R;		/* グー(Rock)で勝った場合の点数		*/
	int		S;		/* チョキ(Scissors)で勝った場合の点数	*/
	int		P;		/* パー(Paper)で勝った場合の点数	*/
	char		T[100005];	/* 筐体側の入力				*/
	char		U[100005];	/* ユーザー側の入力			*/
	int		index;		/* 配列のインデックス			*/
	int		result;		/* 合計点数を保存する			*/
	int	zero_r;			/* Rockでの0点手			*/
	int	zero_s;			/* Scissorsでの0点手			*/
	int	zero_p;			/* Paperでの0点手			*/
	
	/* 入力 */
	scanf("%d %d", &N, &K);
	scanf("%d %d %d", &R, &S, &P);
	scanf("%s", &T);

	result = 0;
	zero_r = 0;
	zero_s = 0;
	zero_p = 0;

	/* ユーザー側のKの値を考えない場合の最善手を入力する */

	for(index = 0; index < N; ++index){
		if(T[index] == 'r')
			U[index] = 'p';
		else if(T[index] == 's')
			U[index] = 'r';
		else if(T[index] == 'p')
			U[index] = 's';
	}
	/* これをTにコピーする */
	
	strcpy(T, U);

	/*
	 * 配列の処理を添え字Kからスタートする
	 * K個前の手と全く同じ手があれば現在の手に変更を加える
	 * K個先の手と比べて違う手を選ぶように処理をする	
	 *------------------------------------------------------------------
	 * if文内で条件として扱っている値を操作するとスタックオーバーフロー
	 * が発生するのでUser入力に値をコピーした
	 */

	for(index = K; index < N; ++index){
		if((T[index] == T[index - K]) && (T[index] == 'r')){

			if(T[index + K] == 's'){
				U[index] = 'p';
				++zero_p;
			}
			else if(T[index + K] == 'p'){
				U[index] = 's';
				++zero_s;
			}
			else{
				U[index] = 'p';
				++zero_p;	
			}
		}
		else if((T[index] == T[index - K]) && (T[index] == 's')){

			if(T[index + K] == 'r'){
				U[index] = 'p';
				++zero_p;
			}
			else if(T[index + K] == 'p'){
				U[index] = 'r';
				++zero_r;
			}
			else{
				U[index] = 'r';
				++zero_r;
			}
		}
		else if((T[index] == T[index - K]) && (T[index] == 'p')){

			if(T[index + K] == 'r'){
				U[index] = 's';
				++zero_s;
			}
			else if(T[index + K] == 's'){
				U[index] = 'r';
				++zero_r;
			}
			else{
				U[index] = 's';
				++zero_s;
			}
		}
      	/* Update */
      	strcpy(T, U);
	}
	/*
	 * ユーザーの手に対する点数をresultに加算していく
	 */
	for(index = 0; index < N; ++index){
		if(U[index] == 'r')
			result += R;
		else if(U[index] == 's')
			result += S;
		else if(U[index] == 'p')
			result += P;
	}
	result -= (R * zero_r);
	result -= (S * zero_s);
	result -= (P * zero_p);
	printf("%d\n", result);
	return (0);
}
/*
 * zero_rをshort intにしていたためテストケース41で範囲が足りなくなりWA
 */

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

int main(int argc, char const *argv[]) {
  int a, b;
  int ans;
  cin >> a >> b;

  if ((a + b) % 2 == 0) {
    ans = (a + b) / 2;
    cout << ans << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	int n; cin >> n;
	vi a(n); rep(i,n) cin >> a[i];
   	map <int,int> ma;
	rep(i,n) ma[a[i]]++;
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	reverse(all(a));
	ll f = -1;
	rep(i,n){
		if(ma[a[i]] >= 4 && f == -1){
			cout << ll(a[i])*a[i] << endl;
			return 0;
		}
		if(ma[a[i]] >= 2 && f != -1){
			cout << f*a[i] << endl;
			return 0;
		}
		if(ma[a[i]] >= 2 && f == -1){
			f = a[i];
		}
	}
	cout << 0 << endl;
	return 0;
}



Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define MOD 1000000007
int main(){
  int n,m;
  cin >>n>>m;
  vector<bool> b(n+1);
  vector<long long int> dp(n+2,0);
  rep(i,m){
    int tmp=0;
    cin >>tmp;
    b[tmp]=true;
  }
  dp[0]=b[0] ? 0:1 ;dp[1]=b[1]? 0:1;
  for (int i=2;i<n+1;i++){
    dp[i]=(dp[i-2]+dp[i-1])%MOD;
    if (b[i]) {
      dp[i]=0;
    }
  }
  cout <<dp[n]<<endl;
}

Measured memory_bytes: 1024
// https://atcoder.jp/contests/abc075/tasks/abc075_c

#include "algorithm"
#include "bitset"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define unless(cond) if (!(cond))
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

struct UnionFind {
  vector<ll> parents;

  UnionFind(ll n) : parents(vector<ll>(n, -1)) {}

  ll root(ll a) {
    if (parents[a] < 0) {
      return a;
    }

    auto r = root(parents[a]);
    parents[a] = r;
    return r;
  }

  bool same(ll a, ll b) { return root(a) == root(b); }

  void merge(ll a, ll b) {
    ll ar = root(a);
    ll br = root(b);

    if (ar == br) {
      return;
    }

    // make less index one as a root
    if (ar > br) {
      swap(ar, br);
    }

    parents[ar] += parents[br];
    parents[br] = ar;
  }

  ll size(ll a) { return -parents[a]; }

  ll group_count() {
    ll res = 0;

    for (auto s : parents) {
      if (s < 0) {
        res++;
      }
    }

    return res;
  }
};

void solve() {
  ll N, M;
  cin >> N >> M;

  VVL edge_list(N, VL());

  rep(i, M) {
    ll a, b;
    cin >> a >> b;
    a--, b--;

    edge_list[a].push_back(b);
    edge_list[b].push_back(a);
  }

  ll res = 0;

  rep(edge_from, N) for (auto edge_to : edge_list[edge_from]) {
    unless(edge_from < edge_to) continue;

    UnionFind uf(N);

    rep(u, N) for (auto v : edge_list[u]) {
      unless(u < v) continue;
      if (u == edge_from && v == edge_to) continue;

      uf.merge(u, v);
    }

    if (uf.group_count() == 2) res++;
  }

  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

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

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

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


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

using namespace std;

long long A[2000],B[2000];
long long dp[100000];
int main(void)
{
    // freopen("aaa.in","r",stdin);
    long long H,N;
    scanf("%lld%lld",&H,&N);
    for (int i=1;i<=N;i++) scanf("%lld%lld",&A[i],&B[i]);
    for (int i=0;i<=H+10001;i++) dp[i] = -1;
    dp[0] = 0;      
    for (int i=1;i<=N;i++)
        for (int j=0;j<=H+10001;j++)
        {
            if (j-A[i]>=0&&dp[j-A[i]]!=-1) 
            {
                if (dp[j]==-1) 
                    dp[j] = dp[j-A[i]]+B[i];
                else
                dp[j] = min(dp[j],dp[j-A[i]]+B[i]);
            // cout<<j<<" "<<i<<" "<<dp[j]<<endl;
            }
        }
    long long ans = 0x7fffffff;
    for (int i=H;i<=H+10001;i++){
        if (dp[i]!=-1) {
            // cout<<i<<endl;
            ans = min(ans,dp[i]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
unsigned long long inf = (1LL << 62);
ll mod = 1000000007;

//bool operator< (pint a, pint b) {
	//return a.second < b.second;

//}



ll gcd(ll a, ll b) {

	if (b == 0)
		return a;

	return gcd(b, a % b);


}

ll max(ll a, ll b) {
	if (a < b) {
		return b;
	}
	else
		return a;

}

ll min(ll a, ll b) {
	if (a < b)
		return a;

	return b;
}




pint dx[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

vector<pint> list;










void floyd(int N, ll** d) {

	rep(k, N+1){
		rep(i, N+1) {
			if (d[i+1][k+1] == inf) continue;
			rep(j, N+1) {
				if (d[j+1][k+1] == inf) continue;

				d[i+1][j+1] = min(d[i+1][j+1], d[i+1][k+1] + d[j+1][k+1]);

			}

		}
	}




}


ll vis[100005];
ll d[100005];
vector<ll> M[100005];
vector<ll> anslist;


stack<int> to_1;

ll col[100005];

void dfs(ll K, ll dist) {

	
	d[K] = dist;
	vis[K] = 1;

		
	for (int i = 0; i < M[K].size(); i++) {
		if (vis[M[K][i]] == 0) {
			
			dfs(M[K][i], dist + 1);
			
		}
	}

}



vector<unsigned long long> v;
ll C[51][51];



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

	rep(i, N) {
		cin >> x;
		v.push_back(x);
	}


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

	
	double maxsum = 0.0;
	rep(i, A) {
		maxsum += v[v.size() - i - 1];

	}


	rep(i, 51) {
		C[i][0] = 1;
		C[i][1] = i;
	}

	for (int j = 2; j <= 50; j++) {
		C[j][j] = 1;
		for (int i = 2; i <= j-1; i++) {
			C[j][i] = (C[j-1][i] + C[j - 1][i - 1]);

		}
	}

	
	printf("%.12f\n", maxsum / (double)A);

	
	ll a = v[v.size() - A];
	ll index = 0;


	rep(i, N) {
		if (v[i] == a) {

			index = i;
			break;
		}

	}
	int lindex = 0;
	for (lindex = index; lindex < v.size() && v[lindex] == a; lindex++) {}


	if (lindex != v.size()) {


		cout << C[lindex - index][lindex - (v.size() - A)] << endl;

	}

	unsigned long long ansum = 0;
	if (lindex == v.size()) {

		for (int j = A; j <= min(B, lindex-index); j++) {
			ansum += C[lindex - index][j];
		}
		cout << ansum << endl;
	}


	



	return 0;
	
}

Measured memory_bytes: 3584
n = int(input())
a = list(map(int,input().split()))
ret = 0
for i in range(n):
    min_i = i
    for j in range(i+1,n):
        if a[j] < a[min_i]:
            min_i = j
    if i!= min_i:
        ret += 1
        a[i],a[min_i]=a[min_i],a[i]
print(" ".join(map(str,a)))
print(ret)



Measured memory_bytes: 5596
import java.io.*;
import java.util.Scanner;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();
		int h = sc.nextInt();
		int w = sc.nextInt();
		
		int[] a = new int[n];
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}

		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] >= h && b[i] >= w) {
				ans++;
			}
		}
		
		pr.println(ans);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define size_of(a) (int)(a).size()
#define allof(a) (a).begin(),(a).end()

int n[9];
char c[9];

vector< int > vec[3];
bool use[9];

bool check() {
	for_(i,0,3) {
		int a1 = vec[i][0], a2 = vec[i][1], a3 = vec[i][2];
		if (c[a1] != c[a2] || c[a2] != c[a3] || c[a3] != c[a1]) return false;
		if (n[a1] == n[a2] && n[a2] == n[a3]) continue;
		vector< int > nums;
		for_(j,0,3) nums.push_back(n[vec[i][j]]);
		sort(allof(nums));
		if (nums[2] - nums[1] == 1 && nums[1] - nums[0] == 1) continue;
		return false;
	}
	
	return true;
}

bool rec(int div, int cnt) {
	if (div == 3) return check();
	
	for_(i,0,9) {
		if (use[i]) continue;
		vec[div].push_back(i);
		use[i] = true;
		++cnt;
		if (rec(cnt == 3 ? div + 1 : div, cnt == 3 ? 0 : cnt)) return true;
		vec[div].pop_back();
		use[i] = false;
		--cnt;
	}
	
	return false;
}

int main() {
	int T;
	cin >> T;
	
	for_(i,0,T) {
		memset(use, 0, sizeof(use));
		for_(i,0,3) vec[i].clear();
			
		for_(j,0,9) cin >> n[j];
		for_(j,0,9) cin >> c[j];

		cout << (rec(0, 0) ? 1 : 0) << endl;
	}
}

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

int kadotani(int s){
    if(s%2==0){return s/2;}
    else{return 3*s+1;}
}



void solve(int s){
    int N=1000001;
    int A[N];
    int temp=s;
    int ans=0;
    for(int i=0;i<N;i++){
        A[i]=0;
    }
    for(int j=1;j<N;j++){
        if(A[temp]==0){A[temp]++;temp=kadotani(temp);}
        else{ans=j;break;}
    }
    printf("%d\n",ans);
}


int main(){
    int s;
    scanf("%d",&s);
    solve(s);
    return 0;
}


Measured memory_bytes: 4096
H, W, A, B = [int(x) for x in input().split()]
M = [[0] * W for _ in range(H)]
M2 = [[0] * H for _ in range(W)]

f = 0
for h in range(H):
  if h < B:
    print('1' * A + '0' * (W - A))
  else:
    print('0' * A + '1' * (W - A))


Measured memory_bytes: 19828
#include<stdio.h>
#define MAX 100010
#define NIL -1

struct Node
{
  int p;
  int l;
  int r;
};

struct Node T[MAX];
int n,D[MAX];

void printkansuu(int);
void depthkansuu(int,int);

int main()
{
  int i,j,d,v,c,l,r;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      T[i].p =T[i].l = T[i].r= NIL;
    }
  for(i=0;i<n;i++)
    {
      scanf("%d%d",&v,&d);
      for(j=0;j<d;j++)
	{
	  scanf("%d",&c);
	  if(j==0)
	    {
	      T[v].l=c;
	    }
	  else
	    {
	      T[l].r=c;
	    }
	  l=c;
	  T[c].p=v;
	}
    }
  for(i=0;i<n;i++)
    {
      if(T[i].p==NIL)
	{
	  r=i;
	}
    }
  depthkansuu(r,0);

  for(i=0;i<n;i++)
    {
      printkansuu(i);
    }
  return 0;
}
  
void printkansuu(int u)
{
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if(T[u].p==NIL)
    {
      printf("root, ");
    }
  else if(T[u].l==NIL)
    {
      printf("leaf, ");
    }
  else
    {
      printf("internal node, ");
    }
  
  printf("[");

  for( i=0,c=T[u].l ; c!=NIL ; i++, c=T[c].r )
    {
      if(i)
	{
	  printf(", ");
	}
      printf("%d",c);
	
    }
  printf("]\n");
}

void depthkansuu(int u,int p)
{
  D[u]=p;
  if(T[u].r!=NIL)
    {
      depthkansuu(T[u].r,p);
    }
  if(T[u].l!=NIL)
    {
      depthkansuu(T[u].l,p+1);
    }
}



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

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	rep(i,n){
		cin >> p[i];
	}
	
	int val = p[0];
	int ans = 0;
	
	REP(i,n-1){
		if(val < p[i]){
			ans++;
		}
		val = min(val,p[i]);
	}
	
	cout << n-ans << endl;
}




Measured memory_bytes: 1024
import sys
import numpy as np

read = sys.stdin.read

N, *A = map(int, read().split())
A = np.array(A, np.int64).reshape(N, N)
'''
answer = 0
for i, j in product(range(N), repeat=2):
    if i < j:
        continue
    edge = A[i][j]
    for k in range(N):
        if i == k or j == k:
            continue

        tmp = A[i][k] + A[k][j]
        if tmp < edge:
            print(-1)
            exit()
        elif tmp == edge:
            break
    else:
        answer += edge
'''

useless = np.zeros_like(A)

for i in range(N):
    grid = A[i] + A[i, None].T
    if np.any(grid < A):
        print(-1)
        exit()
    grid[i] = np.inf
    grid[:, i] = np.inf

    useless |= (A == grid)

print(A[useless != 1].sum() // 2)


Measured memory_bytes: 21952
# Problem: https://atcoder.jp/contests/abc088/tasks/abc088_b
# Python 3rd Try

import sys
# from collections import defaultdict
# import heapq,copy
# from collections import deque


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solver(cardNumberList):
    result = 0
    cardNumberList.sort(reverse=True)

    # algorithm
    # Alices'Turn
    for j in range(0, len(cardNumberList), +2):
        result = result + cardNumberList[j]
    # Bobs'Turn
    for j in range(1, len(cardNumberList), +2):
        result = result - cardNumberList[j]
    return result


if __name__ == "__main__":
    _ = II()
    AI = LI()
    print("{}".format(solver(AI)))


Measured memory_bytes: 3064