akhauriyash/Code-Regression huggingface dataset:
//
//  main.cpp
//  t4
//
//  Created by qi on 2016/10/10.
//  Copyright © 2016年 vinchi. All rights reserved.
//

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int n, m;
    int a[100001];
    long ans;
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    m = 2;
    ans = a[0]-1;
    
    for (int i = 1; i < n; i++) {
        if (a[i] == m) {
            m++;
        } else if (a[i] > m){
            ans += (a[i]-1)/m;
        }
    }
    
    printf("%ld", ans);
    return 0;
}


Measured memory_bytes: 512
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

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

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;

int n;
int ar[300005];
void ng(){
  puts("No");
  exit(0);
}
bool judge(int l,int r){
  int mn=*min_element(ar+l,ar+r),mx=*max_element(ar+l,ar+r);
  if(mn<l || mx>=r) return false;
  for(int i=l+1;i<r;i+=2) if(ar[i]!=i) return false;
  int toR=-1,toL=-1;
  for(int i=l;i<r;i+=2){
    assert(ar[i]!=i);
    if(ar[i]<i){
      if(toL>=ar[i]) return false;
      toL=ar[i];
    }else{
      if(toR>=ar[i]) return false;
      toR=ar[i];
    }
  }
  return true;
}
int main(){
  cin>>n;
  REP(i,n) scanf("%d",&ar[i]),--ar[i];

  REP(i,n) if(ar[i]!=i){
    int j=i;
    while(j<n && ar[j]!=j){
      j+=2;
    }
    if(!judge(i,j-1)){
      ng();
    }
    i=j-2;
  }
  puts("Yes");
  return 0;
}





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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
  ll n;
  cin >> n;
  vector <ll> v(n);
  rep(i, n) {
    ll tmp = 0, a;
    cin >> a;
    while (a%2 == 0) {
      tmp++;
      a /= 2;
    }
    v.at(i) = tmp;
  }
  ll min = v.at(0);
  rep(i, n) {
    if (v.at(i) < min) min = v.at(i);
  }
  cout << min << endl;
}

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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, __VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 100010

string S;

int main()
{
    cin >> S;
    REP(i, S.length() -1) {
        if(S[i] == 'A' && S[i+1] == 'C') {
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)    scanf("%d",&x)
#define sl(x)    scanf("%lld",&x)
#define ss(s)    scanf("%s",s)
#define pi(x)    printf("%d\n",x)
#define pl(x)    printf("%lld\n",x)
#define ps(s)    printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define in insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>    pii;
typedef pair<ll, ll>      pl;
typedef vector<int>       vi;
typedef vector<ll>        vl;
typedef vector<pii>       vpii;
typedef vector<pl>        vpl;
typedef vector<vi>        vvi;
typedef vector<vl>        vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
#define MAXN   20000001 
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}

int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1'000'000'007;
const int N = 3e5, M = N;



void solve(){
    int n,k,i;
    cin>>n>>k;
    int a[n];
    fo(i,n) cin>>a[i];
    sort(a,a+n);
    int ans=0;
    fo(i,k)
    {
        ans+=a[i];
    }
    cout<<ans<<endl;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t = 1;
   // cin >> t;
    while(t--) {
      solve();
    }

    return 0;
}

vl g[N];


int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
    int i, u, v;
    while(m--){
        cin>>u>>v;
    u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }
}

void dfs(int u, int par){
    for(int v:g[u]){
        if (v == par) continue;
        dfs(v, u);
    }
}


Measured memory_bytes: 10692
n = int(input())
a = [int(i) for i in input().split()]
pow_2 = [0] * n
for i in range(n):
    p2 = 0
    while a[i] % 2 == 0:
        p2 += 1
        a[i] //= 2 
    pow_2[i] = p2
print(min(pow_2))

Measured memory_bytes: 3060
#include <iostream>
#include <utility>
#include <stdio.h>

using namespace std;
typedef long long ll;

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



int main(){

    char X;

    scanf("%c",&X);

    if(X>='A'&&X<='Z'){cout<<'A'<<endl;}
    else if(X>='a'&&X<='z'){cout<<'a'<<endl;}

}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define rep(i, start, n) for (int i = (int)(start); i < (int)(n); ++i)
#define all(a) a.begin(), a.end()
#define mp(a, b) make_pair(a, b)

int INF = 100100100;
const int MAX = 110000;
const int MOD = 1000000007;

int main(){
    int N, Q;
    cin >> N;
    ll sum = 0;
    vector<int> a(MAX, 0);
    rep(i, 0, N){
        int num;
        cin >> num;
        sum += num;
        a[num] += 1;
    }
    cin >> Q;
    rep(i, 0, Q){
        int c, d;
        cin >> c >> d;
        sum += (d-c)*a[c];
        a[d] += a[c];
        a[c] = 0;
        cout << sum << endl;
    }
}

Measured memory_bytes: 3732
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    for(int i = 0; i < H; i++) {
      String row = sc.next();
      System.out.println(row);
      System.out.println(row);
    }
  }
}

Measured memory_bytes: 23380
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int Y = sc.nextInt();
		for (int i = 0; i <= X; i++) {
			if (2 * i + (X - i) * 4 == Y) {
				System.out.println("Yes");
				System.exit(0);
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 35752
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vec;
typedef vector<vec> vec2;
typedef map<ll,ll> MPll;
typedef set<ll> setl;

//#define DEBUG

#ifdef DEBUG
#define debug(x) cerr << #x << ":" << x<<"\n"
#define  debugV(V) REP(i,V.size()){cerr << i << ":" << V[i]<<endl;}
#define  debugA(A) REP(i,sizeof(A)/sizeof(ll)){cerr << i << ":" << V[i]<<endl;}
#else
#define debug(x)
#define debugV(x)
#define debugA(x)
#endif

template<class T> inline void amax(T &a,const T &b) { if(a < b) a = b; }
template<class T> inline void amin(T &a,const T &b) { if(a > b) a = b; }




signed main(){
    ll n;
    scanf("%lld",&n);
    getchar();
    ll numE = 0;
    ll numW = 0;
    char s[n];
    for (int i = 0; i < n; ++i) {
        s[i]  = getchar();
        if(s[i] == 'E')  numE++;
    }

    ll ans = 1ll << 60;
    for (int j = 0; j <n ; ++j) {
        if(s[j] == 'E') {
            amin(ans, (--numE) + numW);
        }else{
            amin(ans,numE+numW);
            numW++;
        }
    }

    cout << ans<<endl;

}


Measured memory_bytes: 512
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <tuple> 

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

vector<vector<ll>> e;	
vector<ll> c;

bool color(ll now, ll nowc){
	if(c[now] >= 0 && c[now] != nowc)
		return false;
	c[now] = nowc;
	bool ret = true;
	for(int i=0;i<e[now].size();i++)
		if(c[e[now][i]] != 1-nowc && !color(e[now][i], 1-nowc)){
			ret = false;
			break;
		}
	return ret;
}

int main(){
	ll N,M;
	cin >> N >> M;
	e.resize(N);
	c.resize(N, -1);
	c[0] = 0;
	for(int i=0;i<M;i++){
		ll a,b;
		cin >> a >> b;
		a--; b--;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	bool ok = true;
	ok = color(0, 0);
	if(ok){
		ll zero = 0, one = 0;
		for(int i=0;i<N;i++)
			if(c[i] == 1)
				one++;
			else if(c[i] == 0)
				zero++;
		assert(one + zero == N);
		cout << one * zero - M << endl;
	}else
		cout << N*(N-1)/2 - M << endl;
	return 0;
}

Measured memory_bytes: 7296
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>

using namespace std;

#define ll long long int
#define pii pair<ll,ll>

struct BIT
{
    std::vector<int> bit;
    
    BIT(int size) : bit(size, 0){ }
    
    void add(int k, int x) {
        while (k < bit.size()) {
            bit[k] += x;
            k += k &-k;
        }
    }
    int sum(int k) {
        int res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k&-k;
        }
        return res;
    }
};

struct UnionFind {
    vector<int> data;
    
    UnionFind(int size) : data(size, -1) { }
    
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y)
        {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

vector<vector<pii>> v;
ll score[10000];
int n,m;

ll infi = (ll)1e15;

ll dfs(ll from, ll s, ll depth)
{
    if(depth > 2100)
    {
        return infi;
    }
    ll mm = -infi;
    for(auto e = v[from].rbegin(); e != v[from].rend();e++)
    {
        auto c = e->first + s;
        if(score[e->second] < c)
        {
            score[e->second] = c;
            mm = max(mm, dfs(e->second, c, depth+1));
        }
    }
    if(from == n)
    {
        if(mm == -infi)
        {
            return score[from];
        }
        return max(score[from], mm);
    }
    return mm;
}

#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>
#include <iostream>
#include <string>
#include <cctype>

using namespace std;
vector<ll> a;
vector<ll> sum;

int main(void)
{
    ll n, a, b;
    cin >> n >> a >> b;
    
    if(n <= 1)
    {
        if(a == b)
        {
            cout << 1 << endl;
            return 0;
        }
        cout << 0 << endl;
        return 0;
    }
    if(a > b)
    {
        cout << 0 << endl;
        return 0;
    }
    
    auto lower = a * (n-1) + b;
    auto upper = b * (n-1) + a;
    cout << (upper - lower + 1) << endl;
    return 0;
}

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

int main() {
	long long n, ans;
	std::cin >> n;
	ans = n;
  	
	for (long long i = 1; i <= sqrt(n); i++) {
	    if(n % i == 0){
          long long j = n / i;
          ans = i + j - 2;
        }
	}
	
	std::cout << ans << std::endl;
	
	return 0;
}


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

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

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

	return 0;
}

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

int main() {
  int N=0, A=0, l1=0, l2=0;
  cin >> N;
  
  for(int i=0; i<N; i++){
    cin >> l1 >> l2;
    A+=l2-l1+1;
  }
  
  cout << A << endl;
}

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

int main() {
  string S;
  int N;
  cin >> N >> S;
  string A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  for (int i = 0; i < S.size(); i++) { 
    for (int j = 0; j < 26; j++) {
      if (A.at(j) == S.at(i)) {
        S.at(i) = A.at((j + N)%26);
        break;
      } 
    }
  }
  
  cout << S << endl;

}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#include <numeric> 
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
#define int long long int
#define mod 1000000007
#define INT_BITS 16
#define test int t;cin>>t;while(t--)
#define INF 10000000
#define pi 3.141592
#define watch(x) cout<<(#x)<<"="<<(x)<<"\n" 
#define pb push_back
//#include "debug.cpp"
//__builtin_popcount

int32_t main()
{
    fast
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif
    
    int n;
    cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
        /* code */
    }
    
    int sum=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[i-1])
        {
            sum+=(a[i-1]-a[i]);
            a[i]=a[i-1];
        }
    }
    cout<<sum<<endl;
}


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

int main() {
  int a, b;
  cin >> a >> b;
  cout << max(a+b, max(a-b, a*b)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
(a + b >= 10) ? cout << "error\n" : cout << a + b << "\n";
return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int N;
    cin>> N;
    int a[N];
    for(int i = 0;i < N;i++){
        cin >> a[i];
    }
    for(int i = 0;i < N;i++){
        if(a[i] % 2 == 0){
            if(a[i] % 3 != 0 && a[i] % 5 != 0){
                cout << "DENIED" << endl;
                break;
            }
        }
        if(i == N-1){
            cout << "APPROVED" << endl;
        }
    }

}

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

int main(void){
  
  int a,b,c;
  int temp;
  
  scanf("%d %d %d", &a, &b, &c);
  
  if(b<c){
    temp=b;
    b=c;
    c=temp;
  }
  
  if(a<b){
    temp=a;
    a=b;
    b=temp;
  }
  
  
  printf("%d", 10*a+b+c);
    
    
  return 0;
}


Measured memory_bytes: 1728
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

while(1):
    n,x = li()
    if(n == 0 & x == 0):
        break

    if(x == 0):
        print(0)
        continue

    dp = [[0] * (x+1) for i in range(4)]
    dp [1][1] = 1
    dp[0][0]=1

    for i in range(2,n+1):
        for j in range(x,0,-1):
            for k in range(3,0,-1):
                # print(i,j,k)
                #i個目でi+1以上いれた時の話をしてるとpass
                if(i<k):
                    # print('pass')
                    pass

                # 選んだ選択肢 + 選ばなかった選択肢
                else:
                    if(j-i  >=  0):
                        dp[k][j] =   dp[k][j] + dp[k-1][j-i]

    print(dp[3][x])
    


Measured memory_bytes: 5612
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;


#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>



int main() {
	ll n, k;
	cin >> n >> k;
	string in;
	cin >> in;
	string s = in;
	reverse(ALL(in));
	s += in;
	vector<string> se;
	if (k == 1) {
		REP(i, n + 1) {
			se.push_back(s.substr(i, n));
		}
		sort(ALL(se));
		cout << se[0] << endl;
		return 0;
	}
	k--;
	char c = 'z';
	REP(i, n * 2)if (c > s[i])c = s[i];
	ll ma = 0, now = 0;
	REP(i, n * 2) {
		if (s[i] == c) {
			now++;
			ma = max(now, ma);
		}
		else now = 0;
	}
	ma = max(now, ma);
	ll sz = ma;
	REP(i, k) {
		ma *= 2;
		if (ma >= n) {
			REP(j, n)cout << c;
			cout << endl;
			return 0;
		}
	}
	ll l = n - ma;
	FOR(i, l, n * 2) {
		bool ok = true;
		if (i + sz + 1 < n)continue;
		REP(j, sz) {
			if (i + j >= n * 2 or s[i + j] != c) {
				ok = false;
				break;
			}
		}
		if (ok) {
			string t = s.substr(i - l, l);
			reverse(ALL(t));
			se.push_back(t);
		}
	}
	REP(i, ma)cout << c;
	sort(ALL(se));
	cout << se[0] << endl;
}

Measured memory_bytes: 39552
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
typedef long long ll;
int OO = 0x3f3f3f3f;

ll n, w;
ll wi[100005];
ll va[100005];
ll mem[105][100005];

ll solve(ll x, ll rem)
{
    ll op1, op2;
    if(x == n)
        return 0;
    if(mem[x][rem] != -1)
        return mem[x][rem];

    op1 = solve(x+1, rem);
    op2 = 0;
    if(rem - wi[x] >= 0)
        op2 = solve(x+1, rem-wi[x]) + va[x];
    return mem[x][rem] = max(op1, op2);
}

int main()
{
    memset(mem, -1, sizeof mem);
    cin >> n >> w;
    for(int i = 0; i< n; i++)
    {
        cin >> wi[i] >> va[i];
    }
    cout << solve(0, w) << endl;
    return 0;
}


Measured memory_bytes: 82304
#include<stdio.h>

int main(void){
int m,f,r;
while(scanf("%d %d %d",&m,&f,&r) != EOF){
if(m == -1 && f == -1 && r == -1){
break;
}
else if(m == -1 || f == -1){
printf("F\n");
}
else if((m + f) >= 80){
printf("A\n");
}
else if((m + f) >= 65 && (m + f) < 80){
printf("B\n");
}
else if((m + f) >= 50 && (m + f) < 65){
printf("C\n");
}
else if((m + f) >= 30 && (m + f) < 50 && r >= 50){
printf("C\n");
}
else if((m + f) >= 30 && (m + f) < 50 && r < 50){
printf("D\n");
}
else if((m + f) < 30){
printf("F\n");
}
}
return 0;
}


Measured memory_bytes: 2040
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, M = map(int, input().split())
    ans = 0
    ans += (2 ** M) * ((1900 * M) + (N - M) * 100)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4088
import copy
s=list(map(str,input()))
t=list(map(str,input()))
def converta(s):
  for i in range(len(s)):
    if s[i]=='?':
      s[i]='a'
  return s
res=[]
for i in range(len(s)-len(t)+1):
    c=copy.copy(s)
    ok=True
    for j in range(len(t)):
        if t[j]!=s[i+j] and s[i+j]!='?':
            ok=False
            break
        else:
            c[i+j]=t[j]
    if ok:
        res.append(''.join(converta(c)))
if res==[]:
  print('UNRESTORABLE')
else:
  print(sorted(res)[0])

Measured memory_bytes: 39152
while True:
    height, width = map(int, input().split())
    if height == 0 or width == 0:
        break

    for h in range(0, height):
        for w in range(0, width):
            if 0 < h and h < height - 1 and 0 < w and w < width - 1:
                print('.', end='')
            else:
                print('#', end='')
        print()
    print()




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

/*
   AtCoder contests
   coder : yoichion
 */

public class Main {
    public static String repeat(String s, int t){
        String ans = "";
        for(int i=0;i<t;i++) ans = ans + s;
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int D = sc.nextInt();
        System.out.println("Christmas"+ repeat(" Eve",25-D));
    }
}

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

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

using namespace std;

int main(){
	int n,a[100000]; cin>>n;
	map<int,int> f;
	rep(i,n){
		int a; cin>>a;
		++f[a];
	}

	vector<int> b{0,0};
	for(auto x:f) if(x.second>=2) {
		while(x.second>=2){
			b.emplace_back(x.first);
			x.second-=2;
		}
	}

	sort(b.rbegin(),b.rend());
	cout<<1LL*b[0]*b[1]<<endl;

	return 0;
}


Measured memory_bytes: 4992
using System;
using System.Collections.Generic;

class A
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        string[] s = Console.ReadLine().Split(' ');
       
       List<int> p = new List<int>();

        for (int i = 0; i < n; i++)
        {
            p.Add(int.Parse(s[i]));
        }

        int count = 0;
        int min = p[0];

        for (int i = 0; i < n; i++)
        {
           if (p[i] <= min)
           {
                count++;
                min = p[i];
           }
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 35420
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
using namespace std;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+1;
const int mod = 998244353;
int antitr(int n){
	int gg=n;gg*=2;
	int ans;
	gg=sqrt(gg);
	ans=gg;
	gg*=gg+1;
	gg/=2;
	if(n>=gg) return ans;
	else return ans-1;
}
int solve(ll n){
	int ans=0;
	for(int i = 2; i <= sqrt(n); i++){
		int temp=0;
		while(n%i==0){
			n/=i;temp++;
		}
		ans+=antitr(temp);
	}
	if(n>1) ans++;
	return ans;
}
int main() {
//	freopen(".in","r",stdin);freopen(".out","w",stdout);
	ll n;
	slld(n);
	pd(solve(n));
	return 0;
}

Measured memory_bytes: 3808
import math

N, K = map(int, input().split(' '))
ans=0
# 1からNまでのどれかがでる、そっから倍々にしてKに
for i in range(1,N+1):
    t=max(0,math.ceil(math.log2(K/i)))
    ans+=(0.5**t)/N
print(ans)


Measured memory_bytes: 3188
/* Dsingh_24 */
 
#include<bits/stdc++.h>
#define ll          int
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
 
#define N  100005
int main()
{
	ios
	ll n,i,j;
	cin>>n;
	ll a[n+1],b[n+1]={0};
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=n;i>0;i--){
		ll sum=0;
		for(j=i;j<=n;j+=i)
			sum+=b[j];
		if(sum%2!=a[i])b[i]=1;
	}
	vi ans;
	for(i=1;i<=n;i++)
		if(b[i]==1)
			ans.pb(i);
	cout<<ans.size()<<"\n";
	for(i=0;i<ans.size();i++)cout<<ans[i]<<" ";
	return 0;
}

Measured memory_bytes: 3192
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var S = input[1].split("");
  var cnts=0;
  var cnt=[0];
  var ans=N;
  for(var i=0;i<N;i++){
    if(S[i]=="#"){
      cnts++;
      cnt.push(cnts);
    }else{
      cnt.push(cnts);
    }
  }
  for(var i=0;i<N+1;i++){
    ans=Math.min(cnt[i]+N-i-(cnt[N]-cnt[i]),ans);
  }

  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 15424
#include <stdio.h>


int main(){
	
	int n , a[101] , i , j , count = 0;
	scanf("%d",&n);
	
	for( i = 0 ; i < n ; i++ ){
		scanf("%d",&a[i]);
	}
	for( i = 0 ; i < n ; i++ ){
		for( j = i + 1 ; j < n ; j++ ){
			if( a[i] == a[j] ){
				if(a[i]==0){break;}
				count = count + 1;
				a[j] = 0;
			}
		}
	}
	
	printf("%d\n",n - count);
	
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
using ld = long double;
#define vpl vector<pair<long long,long long>>
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
long long MOD = 1000000007;
const long double pi = 3.1415926535897932;
#define pb push_back
#define mp make_pair
#define mt make_tuple
//(mod m)でのaの逆元を計算する
//a/b(mod m)=a(mod m)*modinv(b,m)
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

//最大最小の入れ替え
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;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる

//ここから
int main(){
    ll A,B,C;
    cin>>A>>B>>C;
    if(A+B>=C){
        cout<<B+C<<endl;
    }else{
        cout<<A+B*2+1<<endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    bool flg[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
        flg[i]=false;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(flg[i]==false&&flg[a[i]-1]==false){
            if(i == a[a[i]-1]-1){
                flg[i]=true;
                flg[a[i]-1]=true;
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 768
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> position(n + 1);
	FOR(i, 0, n) {
		scanf("%d", &a[i]);
		position[a[i]] = i;
	}
	set<int> border = { -1, n };
	long long sumx = 0;
	FOR(i, 1, n + 1) {
		int nowpos = position[i];

		auto pos = border.upper_bound(nowpos);
		int ub = *pos;
		int lb = *(--pos);

		long long left = nowpos - lb - 1;
		long long right = ub - nowpos - 1;
		if (left < right)
			swap(left, right);

		long long toadd = (long long)i*(right + 1)*(left + 1);
		sumx += toadd;
		border.insert(nowpos);
	}
	cout << sumx << endl;


	return 0;
}

Measured memory_bytes: 11136
////////////////////////////////////////////
///                                      ///
///        Template ver. 1.2. rapel      ///
/// Fear is Temporary, Regret is Forever ///
///          Must Try and Get AC         ///
///                                      ///
////////////////////////////////////////////
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>

#include <math.h>
#include <complex>

#include <assert.h>
#include <time.h>
//#include <chrono>
//#include <random>

#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>

#define F first
#define S second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define endl '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}

void hora(int tc) {
	ll a, b;
	cin>>a>>b;
	ll gc = __gcd(a, b);
	cout<<a / gc * b<<endl;
}

int main(){
	desperate_optimization(10);
	int ntc = 1;
	//cin>>ntc;
	for(int tc = 1;tc <= ntc;tc++) hora(tc);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

//int main() {
//	long long a, b, x;
//	cin >> a >> b >> x;
//	long long ans = 0;
//	long long d = 10;
//
//	for (int i = 0;i < 10;i++) {
//		if (x < a * (long long)pow(10, i) + b * ((long long)i + (long long)1)) {
//			d = i;
//			break;
//		}
//	}
//
//	if (d == 0) {
//		cout << 0 << endl;
//		return 0;
//	}
//
//	x -= b * d;
//	ans = x - b*d / a;
//	if (ans > 1000000000) {
//		ans = 1000000000;
//	}
//
//	cout << ans << endl;
//
//	return 0;
//}

int main() {
	int n;
	cin >> n;
	vector<int> x(n + 1);
	vector<int> y(n + 1);
	int j[8] = { 1,2,3,4,5,6,7,8 };
	for (int i = 1;i <= n;i++) {
		cin >> x[i] >> y[i];
	}

	long double distance = 0;
	double cnt = 0;

	do {
		for (int i = 0; i < n - 1; i++) {
			distance += sqrt(pow(x[j[i]] - x[j[i + 1]], 2) + pow(y[j[i]] - y[j[i + 1]], 2));
		}
		cnt++;
	} while (next_permutation(j, j + n));

	distance /= cnt;

	printf("%.10llf", distance);

	return 0;
}


Measured memory_bytes: 3800
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);
parse_tuple!(A, B, C, D);
parse_tuple!(A, B, C, D, E);

// ===

fn main() {
    let (n, k): (usize, usize) = read();
    let mut ng = 0;
    for t in readnc::<usize>() {
        ng |= 1<<t;
    }

    for w in n..n*100 {
        if is_ok(w, ng) {
            println!("{}", w);
            break;
        }
    }
}

fn is_ok(w: usize, ng: usize) -> bool {
    let mut w = w;
    while w >= 1 {
        let d = w % 10;
        if (1<<d)&ng >= 1 {
            return false;
        }
        w /= 10;
    }
    return true;
}


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

typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<ll> march(5);
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        if(s[0] == 'M') march[0]++;
        else if(s[0] == 'A')  march[1]++;
        else if(s[0] == 'R') march[2]++;
        else if(s[0] == 'C') march[3]++;
        else if(s[0] == 'H') march[4]++;
    }
    
    ll ans = 0;
    for(int bit=0; bit<(1<<5); bit++){
        vector<int> v;
        for(int i=0; i<5; i++){
            if(bit & (1<<i)) v.push_back(i);
        }
        if(v.size() == 3){
            ans += march[v[0]] * march[v[1]] * march[v[2]];
        }
    }
    cout << ans << endl;


    return 0;
}

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

int main() {
	int d;
	cin >> d;
	vector<int>c(26);
	for (int i = 0; i < 26; i++)cin >> c.at(i);
	vector<vector<int>>s(d, vector<int>(26));
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < 26; j++)cin >> s.at(i).at(j);
	}
	vector<int>t(d);
	for (int i = 0; i < d; i++)cin >> t.at(i);
	ll ans = 0;
	vector<int>angry(26, 0);
	for (int i = 0; i < d; i++) {
		int x = t.at(i) - 1;
		ans += s.at(i).at(x);
		for (int j = 0; j < 26; j++) {
			if (j == x)angry.at(j) = 0;
			else {
				angry.at(j)++;
				ans -= angry.at(j) * c.at(j);
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3648
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// #define ll long long 
#define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9+7;
int mpow(int a,int b,int p=MOD){a=a%p;int res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
const int N=1e6+2;
map<int,int> ma;
int dfs(int x)
{
	if(x==0) return 0;
	if(ma.count(x)) return ma[x];
	return ma[x]=1+dfs(x/2)+dfs(x/2);
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int h;
	cin>>h;
	cout<<dfs(h);
}
// I never lose. I either win or I learn

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ls rt << 1
#define rs rt << 1 | 1
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define rep(i, x, y) for(int (i) = (x); (i) <= (y); (i) ++)
#define eps 1e-9
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int N = 100010;
struct edge
{
	int s,t,next;
}e[N << 1];
int head[N], cnt;
void insert(int s,int t)
{
	e[cnt].s = s;
	e[cnt].t = t;
	e[cnt].next = head[s];
	head[s] = cnt ++;
	e[cnt].s = t;
	e[cnt].t = s;
	e[cnt].next = head[t];
	head[t] = cnt ++;
}
int n, u, v;
int sg[N];
void dfs(int x, int fa)
{
	sg[x] = 0;
	for (int i = head[x]; i != -1; i = e[i].next)
		if (e[i].t != fa)
		{
			dfs(e[i].t, x);
			sg[x] ^= (sg[e[i].t] + 1);
		}
}
int main()
{
	n = read();
	memset(head, 0xff, sizeof(head));
	cnt = 0;
	rep(i, 1, n - 1)
	{
		u = read();
		v = read();
		insert(u, v);
	}
	dfs(1,1);
	puts(sg[1] == 0 ? "Bob" : "Alice");
	return 0;
}

Measured memory_bytes: 8064
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		Character[] let = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		int[] enc = new int[30];
		String caca = scn.next();
		for(int i = 0;i<caca.length();i++) {
			for(int i2 = 0;i2<let.length;i2++) {
				if(let[i2]==caca.charAt(i)) {
					enc[i2]++;
				}
			}
		}boolean f = true;
		for(int i = 0;i<30;i++) {
			if(enc[i]%2==1)f=false;
		}
		if(f)System.out.println("Yes");
		else System.out.println("No");
		scn.close();
	}
}

Measured memory_bytes: 22996
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10**18] * (H + 1)
dp[0] = 0
for a, b in AB:
    for h in range(H + 1):
        r = min(H, h + a)
        if dp[r] > dp[h] + b:
            dp[r] = dp[h] + b
print(dp[H])


Measured memory_bytes: 43612
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

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

const int mod = 1000000007;

int alphas[26];

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

  int h, w;
  cin >> h >> w;

  rep(i, h) {
    string s;
    cin >> s;
    rep(j,w){
      alphas[s[j]-'a']++;
    }
  }
  

  int canK = 0;
  int can2 = 0;

  if (h % 2 && w % 2) {
    canK = 1;
    can2 = (h+w)/2-1;
  } else if (h%2) {
    can2 = w/2;
  } else if (w%2) {
    can2 = h/2;
  }

  rep(i, 26) {
    if (alphas[i]%2) {
      canK--;
    } else if (alphas[i]%4) {
      can2--;
    }
  }

  cout << (canK >= 0 && can2 >= 0 ? "Yes": "No") << endl;
}


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

int main() {
  int N, M;
  cin >> N >> M;
  int time = 0;
  for (int i = 0; i < M; i++) {
    int a;
    cin >> a;
    time += a;
  }
  if (time > N) cout << -1 << endl;
  else {
    cout << N - time << endl;
  }
}

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


int main(){
    ll x;
    cin>>x;
    ll h;
    if(x>=500){
        ll x1 = x/500;
        ll x2 = (x%500)/5;
        cout<<x1*1000+x2*5;
        return 0;
    }
    else {
        ll x3 = x/5;
        cout<<x3*5;
        return 0;
    }
    
    
    
}



Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        int list[][] = new int[3][3]; // 3*3の二次元配列
        // 二次元配列に値を格納
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                list[i][j] = Integer.parseInt(sc.next());
            }
        }
        final int n = Integer.parseInt(sc.next());
        for (int i = 0; i < n; i++) {
            // bの値
            int num = Integer.parseInt(sc.next());
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    // bと一致する値が二次元配列に存在する場合
                    if (list[j][k] == num) {
                        // 該当箇所を0に更新(当たりとして扱う)
                        list[j][k] = 0;
                    }
                }
            }
        }
        // 縦横斜め列のいずれか一列の要素が全て0の場合、ビンゴ達成
        if (checkBingoVertical(list) ||
                checkBingoParallel(list) ||
                checkBingoLeftUpToRightDown(list) ||
                checkBingoRightUpToLeftDown(list)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

        sc.close();
    }

    // ビンゴの縦列
    private static boolean checkBingoVertical(int[][] plist) {
        int verticalsize = plist.length;
        int parallelsize = plist[0].length;
        HashSet<Integer> hs = new HashSet<>();
        for (int i = 0; i < verticalsize; i++) {
            hs.clear();
            hs.add(plist[0][i]);
            for (int j = 0; j < parallelsize; j++) {
                hs.add(plist[j][i]);
            }
            if (hs.size() == 1) {
                return true;
            }
        }
        return false;
    }

    // ビンゴの横列
    private static boolean checkBingoParallel(int[][] plist) {
        int verticalsize = plist.length;
        int parallelsize = plist[0].length;
        HashSet<Integer> hs = new HashSet<>();
        for (int i = 0; i < verticalsize; i++) {
            hs.clear();
            hs.add(plist[i][0]);
            for (int j = 0; j < parallelsize; j++) {
                hs.add(plist[i][j]);
            }
            if (hs.size() == 1) {
                return true;
            }
        }
        return false;
    }

    // ビンゴの斜め列(＼：左上から右下)
    private static boolean checkBingoLeftUpToRightDown(int[][] plist) {
        int size = plist.length;
        HashSet<Integer> hs = new HashSet<>();
        for (int i = 0; i < size; i++) {
            hs.add(plist[i][i]);
        }
        // 1列全て0ならば、HashSetの要素は0のみ格納される
        if (hs.size() == 1) {
            return true;
        }
        return false;
    }

    // ビンゴの斜め列(／：右上から左下)
    private static boolean checkBingoRightUpToLeftDown(int[][] plist) {
        int size = plist.length;
        HashSet<Integer> hs = new HashSet<>();
        for (int i = 0; i < size; i++) {
            hs.add(plist[i][size - 1 - i]);
        }
        if (hs.size() == 1) {
            return true;
        }
        return false;
    }

}


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

int main()
{
  int n;
  while (cin >> n) {
    if (n == 0)
      break;

    vector<string> mass(n);
    for (int i = 0; i < n; ++i)
      cin >> mass[i];

    int ans = 0;
    for (int i = 0; i < n; ++i) {
      vector<int> sum(6, 0);
      // hor, ver
      for (int j = 0; j < n; ++j) {
	if (mass[i][j] == '1') {
	  ++sum[0];
	  ans = max(ans, sum[0]);
	} else {
	  sum[0] = 0;
	}

	if (mass[j][i] == '1') {
	  ++sum[1];
	  ans = max(ans, sum[1]);
	} else {
	  sum[1] = 0;
	}
      }
 
      // diag
      for (int j = 0; i+j < n; ++j) {
	if (mass[i+j][j] == '1') {
	  ++sum[2];
	  ans = max(ans, sum[2]);
	} else {
	  sum[2] = 0;
	}

	if (mass[n-1-i-j][j] == '1') {
	  ++sum[3];
	  ans = max(ans, sum[3]);
	} else {
	  sum[3] = 0;
	}

	if (mass[n-1-i-j][n-1-j] == '1') {
	  ++sum[4];
	  ans = max(ans, sum[4]);
	} else {
	  sum[4] = 0;
	}

	if (mass[i+j][n-1-j] == '1') {
	  ++sum[5];
	  ans = max(ans, sum[5]);
	} else {
	  sum[5] = 0;
	}
      }
    }

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

Measured memory_bytes: 0