akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.util.stream.Collectors;

@SuppressWarnings("unused")
public class Main {
	String fileName = "input.txt";
	final boolean isDebug = false;
	//final boolean isDebug = true;
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	final int MOD = (int)1e9+7;
	final long INF = Long.MAX_VALUE / 2;
	//final int INF = Integer.MAX_VALUE / 2;
	
	void solve() throws Exception{
		int N = in.nextInt(), K = in.nextInt();
		
		if(K == 0){
			System.out.println((long)N*N);
		}else{
			long ans = 0;
			for(int b = K + 1; b <= N; b++){
				long num = N / b;
				int q = N % b;
				ans += num * (b - K);
				if(q >= K) ans += (q - K + 1);
			}
			System.out.println(ans);
		}
	}
	
	/* end solve */
	
	/* main */
	public static void main(String[] args) throws Exception {
		new Main().m();
	}
	
	void m() throws Exception {
		if(isDebug) in = new FastScanner(new FileInputStream(fileName));
		solve();
		out.flush();
	}
	/* end main */
}
/* end Main */

class FastScanner {
	Reader input;

	FastScanner() {this(System.in);}
	FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}
	
	int nextInt() {return (int) nextLong();}

	long nextLong() {
		try {
			int sign = 1;
			int b = input.read();
			while ((b < '0' || '9' < b) && b != '-' && b != '+') {
				b = input.read();
			}
			if (b == '-') {
				sign = -1;
				b = input.read();
			} else if (b == '+') {
				b = input.read();
			}
			long ret = b - '0';
			while (true) {
				b = input.read();
				if (b < '0' || '9' < b) return ret * sign;
				ret *= 10;
				ret += b - '0';
			}
		} catch (IOException e) {
			e.printStackTrace();
			return -1;
		}
	}

	double nextDouble() {
		try {
			double sign = 1;
			int b = input.read();
			while ((b < '0' || '9' < b) && b != '-' && b != '+') {
				b = input.read();
			}
			if (b == '-') {
				sign = -1;
				b = input.read();
			} else if (b == '+') {
				b = input.read();
			}
			double ret = b - '0';
			while (true) {
				b = input.read();
				if (b < '0' || '9' < b) break;
				ret *= 10;
				ret += b - '0';
			}
			if (b != '.') return sign * ret;
			double div = 1;
			b = input.read();
			while ('0' <= b && b <= '9') {
				ret *= 10;
				ret += b - '0';
				div *= 10;
				b = input.read();
			}
			return sign * ret / div;
		} catch (IOException e) {
			e.printStackTrace();
			return Double.NaN;
		}
	}

	char nextChar() {
		try {
			int b = input.read();
			while (Character.isWhitespace(b)) {
				b = input.read();
			}
			return (char) b;
		} catch (IOException e) {
			e.printStackTrace();
			return 0;
		}
	}

	String nextStr() {
		try {
			StringBuilder sb = new StringBuilder();
			int b = input.read();
			while (Character.isWhitespace(b)) {
				b = input.read();
			}
			while (b != -1 && !Character.isWhitespace(b)) {
				sb.append((char) b);
				b = input.read();
			}
			return sb.toString();
		} catch (IOException e) {
			e.printStackTrace();
			return "";
		}
	}
}

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

int main(){
    double q;
    while(cin >> q, q!=-1){
        double x = q/2;
        while(abs(pow(x, 3)-q)>=0.00001*q){
            x = x - (pow(x, 3)-q)/(3*pow(x, 2));
        }
        printf("%lf\n", x);
    }
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
#define MAX_C 400
#define MAX_N 25000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, c, a[MAX_N+5]; bool flag, mrk[MAX_C+5];
lnt f[MAX_N+5][MAX_C+5], g[MAX_N+5][MAX_C+5]; int lp, rp;
lnt pw(lnt x, int k) {
	lnt ret = 1;
	for (; k; k >>= 1, x = x*x%P)
		if (k&1) ret = ret*x%P;
	return ret;
}
int main() {
	read(n), read(c), read(m);
	lnt tot = pw(c, n-m)*(n-m+1)%P;
	for (int i = 1; i <= m; i++) read(a[i]);
	for (int l = 1; l+c-1 <= m; l++) {
		memset(mrk, false, sizeof mrk);
		for (int r = l; r <= l+c; r++)
			if (r == l+c) flag = true;
			else if (mrk[a[r]]) break;
			else mrk[a[r]] = true;
		if (flag) return printf("%lld\n", tot), 0;
	}
	for (int i = 1; i < c; i++) f[0][i] = 1, g[0][i] = i;
	for (int i = 1; i <= n; i++) for (int j = 1; j < c; j++)
		f[i][j] = (f[i-1][j+1]*(c-j)%P+g[i-1][j])%P, g[i][j] = (f[i][j]+g[i][j-1])%P;
	memset(mrk, false, sizeof mrk); for (int i = 1; i <= m; i++) if (mrk[a[i]]) break; else mrk[a[i]] = true, lp = i;
	memset(mrk, false, sizeof mrk); for (int i = m; i >= 1; i--) if (mrk[a[i]]) break; else mrk[a[i]] = true, rp = i;
	for (int l = 1, r = m; r <= n; l++, r++)
		if (lp == m) {
			lnt cnt = 1;
			for (int i = r+1; i < l+c && i <= n; i++)
				(tot += P-f[l-1][i-l]*g[n-i][i-l]%P*cnt%P) %= P, 
				(cnt *= c-m-(i-r-1)) %= P;
			if (n+1 < l+c) (tot += P-f[l-1][n-l+1]*cnt%P) %= P;
		} else (tot += P-f[l-1][lp]*f[n-r][m-rp+1]%P) %= P;
	return printf("%lld\n", tot), 0;
}


Measured memory_bytes: 158592
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N;
	in >> N;
	std::vector<LL>a(N), b(N);
	rep(i, N) in >> a[i];
	rep(i, N) in >> b[i];

	LL ans = 0;
	rep(k, 30)
	{
		auto a_ = a, b_ = b;
		LL modL = (1LL << (k + 1)), modS = (1LL << k);
		rep(i, N)
		{
			a[i] %= modL;
			b[i] %= modL;
		}
		std::sort(a.begin(), a.end());
		std::sort(b.begin(), b.end());
		LL cnt = 0;
		rep(i, N)
		{
			auto it1 = std::lower_bound(b.begin(), b.end(), 2 * modS - a[i]);
			auto it2 = std::lower_bound(b.begin(), b.end(), modS - a[i]);
			auto it3 = std::lower_bound(b.begin(), b.end(), 4 * modS - a[i]);
			auto it4 = std::lower_bound(b.begin(), b.end(), 3 * modS - a[i]);
			cnt += (it1 - it2) + (it3 - it4);
		}
		if (cnt % 2 == 1) ans += (1LL << k);
		a = a_, b = b_;
	}

	out << ans << std::endl;
	return 0;
}


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

int N, M;
vector<pair<int, int>> P(100010);
bool compare(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }

int main(void){
    
    cin >> N >> M;
    for(int i = 0; i < M; ++i) cin >> P[i].first >> P[i].second;
    sort(P.begin(), P.begin() + M, compare);
    
    int ans = 0, end = 0;
    for(int i = 0; i < M; ++i){
        if(P[i].first >= end){
            end = P[i].second;
            ++ans;
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int N;
	cin >> N;

	int A[200000];
	rep(i, N) cin >> A[i];
	sort(A, A + N);
	reverse(A, A + N);

	ll kotae = A[0];
	int K = N - 2;
	for (int p = 1; p < N; p++) {
		if (K > 0) {
			kotae += A[p];
			K--;
		}
		if (K > 0) {
			kotae += A[p];
			K--;
		}
	}

	co(kotae);




	Would you please return 0;
}

Measured memory_bytes: 4436
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


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

    int k;
    cin >> k;

    cout << ((k + 1) / 2) * (k / 2) << "\n";

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int POW[11];
int table[105][10],value[105][11];

int main(){

	POW[0] = 1;
	for(int i = 1; i <= 10; i++){

		POW[i] = POW[i-1]*2;
	}

	int N;
	scanf("%d",&N);

	int morning,night;

	for(int store = 0; store < N; store++){
		for(int day = 0; day < 5; day++){

			scanf("%d %d",&morning,&night);
			table[store][2*day] = morning;
			table[store][2*day+1] = night;
		}
	}

	for(int store = 0; store < N; store++){
		for(int i = 0; i <= 10; i++){

			scanf("%d",&value[store][i]);
		}
	}

	int ans = -BIG_NUM,tmp,count;

	bool check[10];

	for(int state = 1; state < POW[10]; state++){
		for(int loop = 0; loop < 10; loop++){
			if(state & (1 << loop)){

				check[loop] = true;
			}else{

				check[loop] = false;
			}
		}

		tmp = 0;

		for(int store = 0; store < N; store++){
			count = 0;
			for(int i = 0; i < 10; i++){
				if(check[i] == true && table[store][i] == 1){
					count++;
				}
			}
			tmp += value[store][count];
		}

		ans = max(ans,tmp);
	}

	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n, k;
        cin >> n >> k;
        int a[n];
        for(int &i : a){
            cin >> i;
        }
        int b[n], sum = 0;
        for(int i = 0; i < n; i++){
            sum += a[i];
            b[i] = sum - (i + 1) * k;
        }
        ordered_set<int> s;
        s.insert(0);
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans += s.order_of_key(b[i] + 1);
            s.insert(b[i]);
        }
        cout << ans << '\n';
    }
}

Measured memory_bytes: 47104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(ll i=0;i<(ll)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
const ll mod=1e9+7;
const ll INF = 1e9;

ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b); 
}

bool is_prime(ll x){
    if(x==1) return false;
    for(ll i=2; i*i<=x;i++){
        if(x%i == 0) return false;
    }
    return true;
}

int main(){
    fast_io
    
    int n, m;
    cin>>n>>m;
    vector<int> k(m), p(m);
    vector<vector<int>> s(10);
    rep(i,m){
        cin>>k[i];
        rep(j, k[i]) {
            int x;cin>>x;
            s[i].push_back(x);
            s[i][j]--;
        }
    }
    rep(i,m) cin>>p[i];

    int ans=0;
    rep(i, 1<<n){
        bool ok=true;
        rep(j, m){
            int c=0;
            for(auto&& id : s[j]){
                if((i>>id)&1){
                    c++;
                }
            }
            c%=2;
            if(c!=p[j]) ok=false;
        }
        if(ok) ans++;
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define dd second
#define mp make_pair
#define pb push_back
#define ff first
#define dd second
#define pp pair<int,int>
using namespace std;
int n;
string s;
int was[26];
pp db[200005][26];

main()
{
    ios_base::sync_with_stdio(false);
    cin >> s; n = s.size();
    for(int i = 0; i < 26; ++i) was[i] = -1;
    was[s[n-1]-'a'] = 1;
    for(int i = 0; i < 26; ++i)
    {
        if(s[n-1] == 'a'+i)
        {
            db[n-1][i] = mp(1e9,-1);
        }
        else
        {
            db[n-1][i] = mp(1,-1);
        }
    }

    for(int i = n-2; i >= 0; --i)
    {
        for(int l = 0; l < 26; ++l)
        {
            if(s[i] == 'a' + l)
            {
                int mini = 1e9;
                for(int ll = 25; ll >= 0; --ll)
                {
                    if(mini >= db[i+1][ll].ff)
                    {
                        db[i][l].ff = db[i+1][ll].ff+1;
                        db[i][l].dd =  i+1;
                        mini = db[i+1][ll].ff;
                    }
                }
            }
            else
            {
                db[i][l] = db[i+1][l];
            }
        }
    }

    //cout << db[0][1].ff << endl;
    //cout << db[0][0].ff << endl;

    int cur = 0;
    while(cur != -1)
    {
        int mini = 1e9; int lit = 26, nextt = 0;
        for(int i = 25; i >= 0; --i)
        {
            if(mini >= db[cur][i].ff)
            {
                lit = i; nextt = db[cur][i].dd; mini = db[cur][i].ff;
            }
        }
        cout << (char)('a' + lit);
        cur = nextt;
    }
}



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

int main() {
  int N;
  
  cin >> N;
  
  int cnt;
  int num;
  for (int i=N; i>0; i--) {
    bool flag=false;
    cnt = 0;
    int ibuff=i;
    num=i;
    while(ibuff/2) {
      if (ibuff==2) {
        flag=true;
        break;
      } else if (ibuff%2) {
        break;
      } else {
        ibuff /= 2;
        cnt++;
      }
    }
    if (flag==true) break;
  }
  
  cout << num << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
  ll arr[1005];
  int n,tc,q,l,r;
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  cin>>tc;
  while(tc--)
  {
    cin>>l>>r>>q;
    cout<<count(arr+l,arr+r,q)<<endl;
  }
}



Measured memory_bytes: 3112
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod


mod = 10**9 + 7
N = 3 * 10**5  #出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

N, M, K = map(int, input().split())

mod = 10**9 + 7

base_n = 0
base_m = 0

for i in range(M):
    if i == 0:
        s = (M * (M - 1) // 2) % mod
    else:
        s += (i - (M - i))
    base_m = (base_m + s + mod) % mod
for i in range(N):
    if i == 0:
        s = (N * (N - 1) // 2) % mod
    else:
        s += (i - (N - i))
    base_n = (base_n + s + mod) % mod
base = (base_m * N * N + base_n * M * M) * g2[2] % mod

ans = base * cmb((N * M) - 2, K - 2, mod) % mod

print(ans)


Measured memory_bytes: 100208
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int N;
vector<int> B;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  B.resize(N-1);
  for (int i = 0; i < N-1; i++) {
    cin >> B[i];
  }
  N--;

  int ans = B[0];
  for (int i = 0; i < N-1; i++) {
    ans += min(B[i], B[i+1]);
  }
  ans += B[N-1];

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
double x[100],y[100];
double distance(double p){
    double sum=0;
    for(int i=0;i<n;i++){
        double w=abs(x[i]-y[i]);
        sum+=pow(w,p);
    }
    return pow(sum,1.0/p);
}

int main(){
    cout<<fixed<<setprecision(12);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    for(int i=0;i<n;i++){
        cin>>y[i];
    }
    cout<<distance(1)<<endl;
    cout<<distance(2)<<endl;
    cout<<distance(3)<<endl;
    double mx=0;
    for(int i=0;i<n;i++){
        mx=max(mx,abs(x[i]-y[i]));
        
    }
    cout<<mx<<endl;
    return 0;
    
}


Measured memory_bytes: 3440
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
  int a[100000];
  int main()
  {
      int sx, sy, tx, ty;
 
	  cin >> sx >> sy >> tx >> ty;
      for(int i=1;i<=ty-sy;i++)
      {
         cout<<"U";
     }
     for(int i=1;i<=tx-sx;i++)
     {
         cout<<"R";
     }
     for(int i=1;i<=ty-sy;i++)
     {
         cout<<"D";
     }
     for(int i=1;i<=tx-sx;i++)
     {
         cout<<"L";
     }
     cout<<"L";
     for(int i=0;i<=ty-sy;i++)
     {
         cout<<"U";
     }
     cout<<"R";
     for(int i=1;i<=tx-sx;i++)
     {
         cout<<"R";
     }
     cout<<"D";
     cout<<"R";
     for(int i=0;i<=ty-sy;i++)
     {
         cout<<"D";
     }
     cout<<"L";
     for(int i=1;i<=tx-sx;i++)
     {
         cout<<"L";
     }
   cout<<"U";
   return 0;
 }

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int h,w;
int mod = 1e9+7;

int main() {
    cin >> h >> w;
    vector<vector<char>> a(h,vector<char>(w));
    REP(i,h){
        REP(j,w){
            cin >> a[i][j];
        }
    }
    vector<vector<ll>> dp(h,vector<ll>(w,0));
    dp[0][0]=1;
    REP(i,h){
        REP(j,w){
            if(a[i][j]=='#'){
                dp[i][j]=0;
            }else{
                if(i>0){
                    dp[i][j]+=dp[i-1][j];
                    dp[i][j]%=mod;
                }
                if(j>0){
                    dp[i][j]+=dp[i][j-1];
                    dp[i][j]%=mod;
                }
            }
        }
    }
    put(dp[h-1][w-1])
    return 0;
}




Measured memory_bytes: 9088
import java.util.Scanner;

class Main{
        public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	
    	String str = scan.nextLine();
    	char[] str_c = new char[str.length()];
    	int num = scan.nextInt();
    	
    	String meirei;
    	String find;
    	int begin;
    	int end;
    	
    	for(int i = 0; i < num; i++){
	    	meirei = scan.next();
	        begin = scan.nextInt();
	        end = scan.nextInt();
	    	
	    	String replace = "";
	    	String change = "";
	    	
	    	for(int k = 0; k < str.length(); k++){
	    		str_c[k] = str.charAt(k);
	    	}
	    	
	    	if(meirei.equals("replace")){
	    		replace = scan.next();
	    	}
	    	
	    	if(meirei.equals("print")){
	    		System.out.println(str.substring(begin, end + 1));
	    	}else if(meirei.equals("reverse")){
	    		find = str.substring(begin, end + 1);
	    		for(int j = find.length() - 1; j >= 0; j--){
	    			change += find.charAt(j);
	    		}
	    		for(int j = begin; j < end + 1; j++){
    				str_c[j] = change.charAt(j - begin);	
    			}
	    		str = String.valueOf(str_c);
	    	}else{
    			for(int j = begin; j < end + 1; j++){
    				str_c[j] = replace.charAt(j - begin);
    				
    			}
	    		str = String.valueOf(str_c);
	    	}
    	}
    	
     }
}

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

#define MAX_N 1100
#define MAX_M 1100

int main(){
	int dp[MAX_N+1][MAX_M+1];
	int n,m,s,x[MAX_N],y[MAX_M];
	memset(dp,127,sizeof(dp));
	memset(x,127,sizeof(x));
	memset(y,127,sizeof(y));
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		cin>>x[i];
	}
	for(int i=1;i<=n;i++){
		cin>>y[i];
	}
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+x[j+1]*y[i+1]);
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

Measured memory_bytes: 5912
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);
ll compute_neg(deque<ll> cost, ll k) {
    ll n = cost.size();
    ll res = INT_MIN;
    ll acc = 0;
    for(int i = 0; i < min(n, k); i++) {
        acc += cost[i%n];
        res = max(res, acc);
    }
    return res;
}
ll compute_pos(deque<ll> cost, ll k, ll sum) {
    ll n = cost.size();
    ll res = INT_MIN;
    ll times = k / n;
    ll acc = 0;
    if (times > 3) {
        ll zip = times-3;
        acc += zip*sum;
        k -= zip*n;
    }
    res = acc; 
    for(int i = 0; i < k; i++) {
        acc += cost[i%n];
        res = max(res, acc);
    }
    return res;
}
int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> perm(n, 0);
    vector<ll> cost(n, 0);
    for(auto& val: perm) {
        cin >> val;
        val -= 1;
    }
    for(auto& val: cost)
        cin >> val;
    vector<vector<int>> grp;
    vector<int> visit(n, 0);
    auto dfs = [&] (auto& self, int src, int cur, vector<int>& st) -> void {
        if (cur == src) {
            grp.push_back(st);
            return;
        }
        st.push_back(cur);
        visit[cur] = 1;
        self(self, src, perm[cur], st);
    };
    for(int i = 0; i < n; i++) {
        if (visit[i] == 0) {
            vector<int> tmp = {i};
            visit[i] = 1;
            dfs(dfs, i, perm[i], tmp);
        }  
    }
    ll ans = INT_MIN;
    for(auto vec: grp) {
        deque<ll> cost2;
        for(int idx: vec) {
            cost2.push_back(cost[idx]);
        }
        ll cycle = vec.size();
        ll acc = accumulate(cost2.begin(), cost2.end(), 0LL);        
            for(int i = 0; i < cycle; i++) {
                if (acc < 0)
                    ans = max(ans, compute_neg(cost2, k));
                else               
                    ans = max(ans, compute_pos(cost2, k, acc));                
                ll head = cost2.front();
                cost2.push_back(head);
                cost2.pop_front();
            }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N, K, A;
  A=1;
  cin >> N >> K;
  for(int i; i<N; i++){
    if (A*2<A+K){
      A*=2;
    }
    else{
      A+=K;
    }
  }
  cout << A << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
#define  pi  pair<int,int>
#define  pb  push_back
#define  F   first
#define  S   second
const int N=2e5+3;
//string s,p;
//vector<int>v;
//map<int,int>mp;

int main()
{
    ft
    ll t,i,j,n,m,l,r;
    char c;
    cin>>n>>c>>m;
    if(c=='+')
    {
        n+=m;
    }
    else
    {
        n-=m;
    }
    cout<<n<<"\n";
    return 0;
}



Measured memory_bytes: 256
while True :
  H, W = map(int, input().split())
  if(H == 0 & W == 0) :
    break
  else :
    for i in range(H) :   #i in range(x) 1つずつカウント。i <= x
      for i in range(W) :
        print("#", end = "")   #最後だけ空白無し
      print()   #改行
    print()


Measured memory_bytes: 7000
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
	int N; scanf("%d", &N);
	int cnt = 0; int prev = 0; int ret = 0;
	for (int i = 0; i < N; i++){
		int h; scanf("%d", &h);
		if (h <= prev){
			cnt++;
			ret = max(ret, cnt);
		}
		else{
			cnt = 0;
		}
		prev = h;
	}

	printf("%d", ret);

	return 0;
}

Measured memory_bytes: 128
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
p = IL()
q = IL()
a = [i for i in range(1,N+1)]

data = list(itertools.permutations(a))
data.sort()

for i in range(len(data)):
  if p == list(data[i]):
    pp = i
  if q == list(data[i]):
    qq = i
print(abs(pp - qq))

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

int main(){
	int a,b;
  	double x,y;
  	cin >> a >> b;
  	x=(a+b)/2.0;
  	y=x-(a+b)/2;
  	if(y>=0.5){
      cout << x-y+1 << endl;
    }else{
      cout << x-y << endl;
    }
}

	

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int a=0,b=0,c=0,k[15],i;
	for(i=1;i<=10;i++){
		scanf("%d",&k[i]);
	}
	for(i=1;i<=10;i++){
		if(a<k[i]){
			c=b;
			b=a;
			a=k[i];
			continue;
		}
		if(b<k[i]){
			c=b;
			b=k[i];
			continue;
		}
		if(c<k[i]){
			c=k[i];
		}
	}
	printf("%d\n%d\n%d\n",a,b,c);
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
using namespace std;
int main() {
	char s[18];
	for (int i = 0; i<19; i++) {
		cin >> s[i];
		if (s[i] == ',')s[i] = ' ';
	}
	for (int j = 0; j<19; j++)cout << s[j];
	cout << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {
	long long int N;

	cin >> N;
	long long int A[6];

	long long int min_val = 99999999999999999;

	for (int i = 1; i <= 5; i++) {
		cin >> A[i];
		if (A[i] < min_val) { min_val = A[i]; }
	}

	long long int ans = N / min_val;

	if (N%min_val != 0) { ans++; }
	ans += 4;

	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;

int main(){
    ll N, K;
    ll A[200002];
    cin>>N>>K;
    for(ll i=1;i<=N; i++){
        cin>>A[i];
    }
    for(ll i=K+1; i<=N; i++){
        if(A[i]>A[i-K]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

Measured memory_bytes: 5196
import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    dp = []
    dp.append(0)
    for n in range(w_limit):
        dp.append(-1)
    for i in treasures:
        for j in range(w_limit - i.weight, -1, -1):
            if dp[j] >= 0:
                dp[j + i.weight] = max(dp[j + i.weight], dp[j] + i.value)
    p = 0
    q = 0
    for i in range(w_limit + 1):
        if dp[i] > p:
            p = dp[i]
            q = i
    return (p, q)






case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

Measured memory_bytes: 4736
#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
  int N;
  std::cin >> N;
  std::vector<int> d(N);
  for (int i = 0; i < N; ++i)
    std::cin >> d[i];
  std::sort(d.begin(), d.end());
  
  std::cout << (d[d.size() / 2] - d[d.size() / 2 - 1]) << std::endl;
}

Measured memory_bytes: 640
def countingsort(A, k):
    C = [0] * (k+1)
    n = len(A)
    
    for i in A:
        C[i] += 1
        
    for i in range(1, k+1):
        C[i] += C[i-1]
        
    B = [0] * n
    for i in A:
        rank = C[i]
        B[rank-1] = i
        C[i] -= 1
        
    return B
    
n = int(input())
A = [int(i) for i in input().split()]

ans = countingsort(A, 10000)
print(" ".join([str(i) for i in ans]))


Measured memory_bytes: 241484
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
#define _USE_MATH_DEFINES


int main()
{
    int n;
    int a[202];
    int count=0;

    scanf("%d",&n);

    for(int i=0;i<n;i++){
	scanf("%d",&a[i]);
    }

    while(true)
    {
	bool exist_odd=false;
	
	for(int i=0;i<n;i++)
	{
	    if(a[i]%2!=0)
		exist_odd=true;
	}

	if(exist_odd==true)
	    break;

	for(int i=0;i<n;i++)
	    a[i]/=2;

	count++;
    }

    printf("%d",count);
    
    return 0;
}




















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

int main(){
    int n;
    int a,b;
    string str,ope,p,s1,s2;
    cin >> str;
    cin >> n;

    for (int i = 0; i < n ; ++i) {
        cin >> ope;
        cin >> a >> b;
        if(ope == "print") {
            cout << str.substr(a,b-a+1) << endl;
        } else if(ope == "reverse"){
            s1 = str.substr(a, b-a+1);
            for(int j=0;j<s1.length();j++){
                str[a+j]=s1[s1.length()-1-j];
            }
        } else if(ope == "replace"){
            cin >> p;
            str = str.replace(a,b-a+1,p);
        }
    }
    return 0;
}

Measured memory_bytes: 1224
/*     *******************Bismillahir Rahmanir Rahim************************
                          MD. ASFAKUL GHANI!
                          *ProMAGFAT*!
 SECRET_warning :)->FAT   CSE-25!
                          JAHANGIRNAGAR UNIVERSITY!
                          Dhaka,Bangladesh!
*/

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

#define           fasterIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define           Im int main()
#define           ll long long
#define           sc scanf
#define           pf printf
#define           rn0 return 0
#define           rn return
#define           f0(i,n) for(ll i=0;i<n;i++)
#define           f1(i,n) for(ll i=1;i<=n;i++)
#define           f2(i,n) for(ll i=n-1;i>=0;i--)
#define           pi 2*acos(0.0)
#define           modulo 1000003
#define           dd double
#define           PI 3.14159265358979
#define           pi 2*acos(0.0)
#define           p_b push_back
#define           ps push

/*
ll for_binarySearch(ll a,ll b,ll aa[],ll x){while(a<=b){ll mid=(a+b)/2;if(aa[mid]==x) return 1;else if(aa[mid] > x) b=mid-1;else a=mid+1;}return -1;}
ll for_gcd(ll a,ll b){if(a==0) return b;else return for_gcd(b%a,a);}
ll for_prime(ll x){for (ll i=2;i*i<=x;i++){if(x%i==0) return 0;}return 1;}
void for_swap(char *x,char *y){char temp;temp=*x;*x=*y;*y=temp;}
ll for_big_mod(ll b,ll p,ll m){if(p==0) return 1;else if(p%2==0){ll k=for_big_mod(b,p/2,m);return (k*k)%m;}else return ((b%m)*(for_big_mod(b,p-1,m)))%m;}
ll for_josephus(ll n,ll k){if(n==1) return 1;return (for_josephus(n-1,k)+k-1)%n+1;}
ll for_gcdExtended(ll a,ll b,ll *x,ll *y){if(a==0){*x=0;*y=1;return b;}ll x1,y1;ll gcd=for_gcdExtended(b%a,a,&x1,&y1);*x=y1-(b/a)*x1;*y=x1;return gcd;}
*/

void debug1()
{
    cout << "***" << endl;
}

void debug11(ll n)
{
    cout << n << endl;
}


ll n,q;
ll par[101000];
ll rnk[101000];
pair <ll,pair<ll,ll> > pp[101010];

void FAT_init()
{
    for (ll i = 0; i < n; i += 1){
        par[i] = i, rnk[i] = 0;
    }
}

ll FAT_find(ll x)
{
    if (x == par[x]) rn x;
    else rn par[x] = FAT_find(par[x]);
}

void FAT_union(ll a, ll b)
{
    ll x = FAT_find(a);
    ll y = FAT_find(b);
    if (rnk[x] > rnk[y]){
        par[y] = x;
    }
    else if (rnk[y] > rnk[x]){
        par[x] = y;
    }
    else {
        par[y] = x;
        rnk[x] += 1;
    }
}

ll FAT_kruskal(pair <ll,pair<ll,ll> > pp[])
{
    ll cnt = 0;
    for (ll i = 0; i < q; i += 1){
        ll c = pp[i].first;
        ll a = pp[i].second.first;
        ll b = pp[i].second.second;
        if (FAT_find(a) != FAT_find(b)){
            cnt+=c;
            //debug11(cnt);
            FAT_union(a,b);
        }
    }

    rn cnt;
}

Im
{
    /*#ifdef FAT
       freopen("input.txt","w",stdin);
    #endif // FAT*/

    //fasterIO;

    cin>>n>>q;
    FAT_init();

    for (ll i = 0; i < q; i += 1){
        ll u,v,w;
        cin>>u>>v>>w;
        pp[i] = make_pair(w,make_pair(u,v));
    }
    sort(pp,pp+q);
    ll c1 = FAT_kruskal(pp);

    cout << c1 << endl;

   // main();

    rn0;
}

Measured memory_bytes: 5632
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) cout << (x) << endl;
#define sz(x) int(x.size())
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

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

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};


ll countMinimalReplacements(string s) 
{ 
    ll n = s.length(); 
  
    ll cnt = 0; 
  
    for (ll i = 1; i < n; i++) { 
 
        if (s[i] == s[i - 1]) { 
            cnt += 1; 
 
            if (i != (n - 1)) { 
 
                for (auto it : "abcdefghijklmnopqrstuvwxyz") { 
                    if (it != s[i + 1] && 
                        it != s[i - 1]) { 
                        s[i] = it; 
                        break; 
                    } 
                } 
            } 
  
            else
            { 
                for (auto it : "abcdefghijklmnopqrstuvwxyz") { 
                    if (it != s[i - 1]) { 
                        s[i] = it; 
                        break; 
                    } 
                } 
            } 
        } 
    } 
  
    return cnt; 
} 

int main(void){
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    REP(i,1,n){
        set<char> st;
        set<char> st2;
        int tmp = 0;
        rep(k,i){
            st.insert(s[k]);
        }
        REP(j, i, n){
            st2.insert(s[j]);
        }
        for (auto it = st.begin(); it != st.end(); it++) {
            if(st2.find(*it) != st2.end()){
                tmp++;
            }
        }
        chmax(ans,tmp);
    }
    print(ans);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
	int k,i,c,len,a1;
	char s[101],a[101];
	scanf("%d %s",&k,s);
	len=strlen(s);
	c=0;
	for(i=0;i<len;i++){
		c++;
	}
	a1=0;
	a1=c-k;
	c=c-a1;
	if(a1>0){
		for(i=0;i<c;i++){
			a[i]=s[i];
		}
		a[c]='\0';
		printf("%s...",a);
	}
	else	printf("%s\n",s);
	return 0;
}


Measured memory_bytes: 1708
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9)
		write(x/10);
    putchar(x%10+'0');
}
int main()
{
	ios::sync_with_stdio(false);
	int a,b,c;
	cin>>a>>b>>c;
	if(a>b) swap(a,b);
	if(a>c) swap(a,c);
	if(b>c) swap(b,c);
	if(a+b==c) puts("Yes");
	else puts("No");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cout << v << " ";                                                          \
  }                                                                            \
  cout << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
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;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vec< int > a(N);
  REP(i, N) cin >> a[i];

  //尺取り法
  int ans = 0;
  vec< bool > flg(20, false);
  int r = 0;
  REP(l, N) {
    while (r < N) {
      bool check = true;
      REP(j, 20) {
        bool p = a[r] & BIT(j);
        if (flg[j] && p) {
          check = false;
          break;
        }
      }
      if (check) {
        REP(j, 20) {
          bool p = a[r] & BIT(j);
          flg[j] = flg[j] || p;
        }
        r++;
      } else {
        break;
      }
    }
    REP(j, 20) {
      bool p = a[l] & BIT(j);
      if (p) {
        flg[j] = false;
      }
    }
    // DEBUG(l);
    //  DEBUG(r);
    ans += r - l;
  }

  print(ans);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;  
  cin >> n >> k ;
 
  int ans = 0;
  int x;
  for (int i=0; i<n; i++) {
    cin >> x;
    ans += min(x*2, (k-x)*2);
  }
 
  cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby
N = gets.chomp.to_i
nums = gets.chomp.split(' ').map(&:to_i)

if nums.include?(0)
    puts 0
    exit
end

ans = 1
nums.each do |num|
    ans = ans * num
    if ans > 1000000000000000000
        ans = -1
        break
    end
end
puts ans

Measured memory_bytes: 23440
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

vector<int> BFS(int s, vector<vector<int>>& G) {
    int V = G.size();
    const int INF = 1e9;
    vector<int> dist(V, INF);
    queue<int> que;
    que.emplace(s);
    dist[s] = 0;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int to : G[v]) {
            if (dist[to] == INF) {
                que.emplace(to);
                dist[to] = dist[v] + 1;
            }
        }
    }
    return dist;
}

signed main() {
    int n, x, y;
    cin >> n >> x >> y;
    x--;
    y--;
    vector<vector<int>> G(n);
    rep(i, n - 1) {
        G[i].emplace_back(i + 1);
        G[i + 1].emplace_back(i);
    }
    G[x].emplace_back(y);
    int ans[n] = {};
    rep(i, n) {
        vector<int> dist = BFS(i, G);
        for (int j = i + 1; j < n; j++) {
            ans[dist[j] - 1]++;
        }
    }
    rep(i, n - 1) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 384
//close stdin
//https://codeforces.com/problemset?order=BY_RATING_ASC&tags=binary+search%2C1300-
#include <bits/stdc++.h>
using namespace std;
long long  gcd(long long  a, long long b){ 
	if (a == 0) 
		return b;  
	return gcd(b % a, a);  
	} 
long long lcmm(long long a,long long b){
	
return (a*b)/gcd(a, b);
}
	
int mod=998244353;
long long summ(long long x){
	long long ans=0;
	while(x!=0){
		ans+=(x%10);
		x=x/10;
	}
	return ans;
	
}
bool prime[1000003]; 
void SieveOfEratosthenes() 
{ 
	int n=1000002;
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 

} 

int main(){
	//freopen ("t.txt","r",stdin);
	int n,w;
	scanf("%d %d",&n,&w);
	vector<vector<long long >> cost(n+1,vector<long long >(w+1,0));
	vector<long long > val(n),weight(n);
	for(int i=0;i<n;i++){
		cin>>weight[i]>>val[i];
	}
	for(int i=0;i<n+1;i++){
		for(int j=0;j<w+1;j++){
			if(i==0 || j==0)
				continue;
			
			if(j>=weight[i-1])
			cost[i][j]=max(val[i-1]+cost[i-1][j-weight[i-1]],cost[i-1][j]);
			else
			{
					cost[i][j]=cost[i-1][j];
			}
			//cout<<i<<" "<<j<<" "<<cost[i][j]<<" "<<val[i-1]<<" "<<j-weight[i-1]<<"\n";
			
		}
	}
	cout<<cost[n][w];


	

	



return 0;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;

#define sp << " " <<
#define mod 1000000007
#define PI 3.14159265358979323
#define y second
#define x first
#define pb push_back
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pqueue priority_queue< ll >
//#define pdqueue priority_queue< ll,vector<ll> ,greater< ll > >
#define codejamDebug(x) cout<<"Case #"<<x<<": ";
#define debug(x) cout<<#x<<" :"<<x<<endl;
#define rep(i,n) for(long long i=0;i<n;i++)
#define f(i,a,b) for(long long i = a; i < b; i++)
#define fd(i,a,b) for(long long i = a; i >=b; i--)
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int           ll;
typedef long double             ld;
typedef unsigned long long int ull;
typedef vector <int>            vi;
typedef vector <ll>            vll;
typedef pair <int, int>        pii;
typedef pair <ll, ll>          pll;
typedef vector < pii >        vpii;
typedef vector < pll >        vpll;
typedef vector <string>         vs;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//Handle:cyber_rajat

int main(int argc, char const *argv[])
{
	sync;
	int n, k;
	cin >> n >> k;
	int a[n+5];
	rep(i,n){
		cin >> a[i];
	}
	sort(a,a+n);
	int sum = 0;
	rep(i,k){
		sum += a[i];
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 3664
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(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 main() {
  int a, b;
  cin >> a >> b;

  int num = 1;
  int res;

  for(int i = 2; i < 1000; i++){
    if(i == b - a){
      res = num + i - b;
      break;
    } else
      num += i;  
  }
  cout << res << ln;
}
  


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n,i,j,k,d;
    ll ans,r=0,g=0,b=0;
    string s;
    cin>>n;
    cin>>s;
    for(i=0;i<(int)s.size();i++)
    {
        if(s[i]=='R')
            r++;
        else if(s[i]=='G')
            g++;
        else
            b++;
    }
    ans=r*g*b;
    for(i=0;i<n;i++)
    {
        for(d=0;d<n;d++)
        {
            j=i+d;
            k=j+d;
            if(k>=n)
                break;
            if(s[i]!=s[j] && s[i]!=s[k] && s[j]!=s[k])
                ans--;

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


Measured memory_bytes: 3636
#include <algorithm>
#include <cassert>
#include <iostream>
#include <list>
#include <map>
#include <vector>
using namespace std;

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  multimap<int, int> obstacles;
  for (int i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    obstacles.insert(make_pair(x, y));
  }
  int max_y = 1;
  int i;
  for (i = 2; i <= H; ++i) {
    using iterator = decltype(obstacles)::iterator;
    pair<iterator, iterator> itrs = obstacles.equal_range(i);
    bool good_obs_found = false;
    bool maxy_canbe_increased = true;
    for (iterator itr = itrs.first; itr != itrs.second; ++itr) {
      if (itr->second <= max_y) {
        good_obs_found = true;
        break;
      } else if (itr->second == max_y + 1) {
        maxy_canbe_increased = false;
      }
    }
    if (good_obs_found) {
      break;
    }
    if (maxy_canbe_increased) {
      max_y++;
    }
  }
  cout << i - 1 << endl;
  return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000;
const int MOD = (int)1e9 + 7;

signed main()
{
    int n, m;
    cin >> n >> m;
    int x = 1900 * m + 100 * (n - m);
    int result = x * pow(2, m);
    cout << result << "\n";
}

Measured memory_bytes: 512
# Q2

N = int(input())
S = input()

def sentenceCount(sx, sy):
    tmp = ''
    count = 0
    for char in sx:
        if sy.count(char) > 0 and not char in tmp:
            count = count + 1
            tmp = tmp + char
    
    return count

cnt = 0
for i in range(1, N):
    tmp = sentenceCount(S[:i], S[i:])
    if tmp > cnt:
        cnt = tmp

print(cnt)

Measured memory_bytes: 3060
#include<stdio.h>
#define N 500000
  
int H;
int A[N+1];
  
void K(int i){
  int l=i*2, r=i*2+1, max, temp=0;
  if(l <= H && A[l] > A[i]){
    max=l;
  }
  else {
    max=i;
  }
  if(r <= H && A[r] > A[max]){
    max=r;
  }  
  if(max != i){
    temp = A[i];
    A[i] = A[max];
    A[max] = temp;
    K(max);
  }
}

void B(){
  int i=0;
  for(i = H/2; i >= 1; i--){
    K(i);
  }
}
  
int main(){
  int i,j;
  scanf("%d", &H);
  for(i = 1; i <= H; i++){
    scanf("%d", &A[i]);
  }
  B();
  for(i = 1; i <= H; i++){
    printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
  
  return 0;
}

Measured memory_bytes: 2552
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int a[4];
  REP(i,4){
    cin >> a[i];
  }

  int ans = 0;
  REP(i,4){
    if(a[i] == 1){
      ans++;
      break;
    }
  }
  REP(i,4){
    if(a[i] == 9){
      ans++;
      break;
    }
  }
  REP(i,4){
    if(a[i] == 7){
      ans++;
      break;
    }
  }
  REP(i,4){
    if(a[i] == 4){
      ans++;
      break;
    }
  }
  if(ans==4){
    cout <<  "YES\n";
  }else{
    cout << "NO\n";
  }
  return 0;
}



Measured memory_bytes: 256