akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1001001001;

ll pow_mod(ll p, ll n, ll m) {
	if (n == 0) return 1;
	else if (n == 1) return p % m;
	else if (n % 2 == 1) return p * pow_mod(p, n - 1, m) % m;
	else {
		ll tmp = pow_mod(p, n / 2, m);
		return (tmp * tmp) % m;
	}
}

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

ll com_mod(ll n, ll k, ll m) {
	if (k == 0) return 1;
	else {
		ll x = 1;
		ll y = 1;
		for (ll i = 0; i < k; i++) {
			x = (x * (n - i)) % m;
			y = (y * (i + 1)) % m;
		}
		ll res = (x * pow_mod(y, m - 2, m)) % m;
		return res;
	}
}

int main() {
	int a, b, h;
	cin >> a >> b >> h;
	cout << (a + b) * h / 2 << endl;
	return 0;
}

Measured memory_bytes: 3600
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
const int maxlongint=2147483647;
const long long mo=1e9+7;	
const int N=2005;
using namespace std;
int n,k;
long long f[N][N],jc[N*N],ny[N*N],ans;
long long poww(long long x,int y)
{
	long long s=1;
	for(;y;y>>=1,x=x*x%mo)
		if(y&1) s=s*x%mo;
	return s;
}
long long C(int m,int n)
{
	if(n>m) return 0;
	return jc[m]*ny[n]%mo*ny[m-n]%mo;
}
int main()
{
	//freopen("agc002f.in","r",stdin);
	//freopen("agc002f.out","w",stdout);
	scanf("%d%d",&n,&k);
	if(k<=1)
	{
		printf("1\n");
		return 0;
	}
	jc[0]=ny[0]=1;
	for(int i=1;i<=n*k;i++) jc[i]=jc[i-1]*i%mo,ny[i]=poww(jc[i],mo-2);
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=i;j>=0;j--)
			f[i][j]=(f[i][j]+f[i-1][j-1]*C(k*i-j-1,k-2)%mo+f[i][j+1])%mo;
	printf("%lld",f[n][0]*jc[n]%mo);
}

Measured memory_bytes: 94464
length = int(input())
first_string, second_string = input().split()
first_list = list(first_string)
second_list = list(second_string)
result_list = []
for i in range(length):
  result_list.append(first_list[i])
  result_list.append(second_list[i])
  
result = "".join(result_list)
print(result)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){return x%y==0?y:gcd(y,x%y);}
int main(){
  int K,T;cin>>K>>T;
  int M=0;
  for(int i=0;i<T;i++){
    int a;cin>>a;
    if(a>M)M=a;
  }
  cout<<max(0,M-(K-M)-1);
}



Measured memory_bytes: 256
#include <algorithm>
#include <chrono>
#include <climits>
#include <cmath>
#include <deque>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using llong = long long;
using ullong = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection)  (collection).begin(), (collection).end()
#define loop(i, times) for (llong i = 0; i < times; i++)
#define rloop(i, times) for (llong i = times -1; 0 <= i; i--)

std::chrono::system_clock::time_point  start;

void TimeStart(void)
{
	start = std::chrono::system_clock::now();
}

void TimeEnd(void)
{
	auto time = std::chrono::system_clock::now() - start;
	auto msec = std::chrono::duration_cast<std::chrono::milliseconds>(time).count();
	cerr << endl << msec << " msec " << endl;
}

#endif


struct Order
{
	llong time_;
	bool operator<(const Order& order) const
	{
		return (time_ % 10) < (order.time_ % 10);
	};
	bool operator>(const Order& order) const
	{
		return (time_ % 10) > (order.time_ % 10);
	};
};

class ABC123B
{
public:
	ABC123B()
	{
		ans_ = 0;
		count_ans_ = 0;
		order_.resize(5);
		loop(i, 5)
			cin >> order_[i].time_;
	}
	void Run(void)
	{
		sort(all(order_), greater<Order>());

		for (const auto & e: order_)
		{
			if (e.time_ % 10 != 0)
				continue;
			ans_ += e.time_;
			count_ans_++;
		}

		loop (i, 5)
		{
			if (order_[i].time_ % 10 == 0)
				continue;

			if (count_ans_ != 4)
			{
				ans_ += order_[i].time_;
				ans_ += (10 - (ans_ % 10));
				count_ans_++;
			}
			else
			{
				ans_ += order_[i].time_;
				count_ans_++;
			}


		}

		cout << ans_;
	}
private:
	vector<Order> order_;
	llong ans_;
	llong count_ans_;
};

int main(void)
{
	ABC123B abc123b;
	abc123b.Run();
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
    int N;
    cin>>N;
    int A;
    double r=0.00000;
    rep(i,N){
        cin>>A;
        r+=1.00000/A;
    }
    double ans=1/r;
    cout<<ans<<endl;
}


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

using namespace std;

#define MAXN 101
typedef pair<int,int> pii;

int check[3][3];

void checalinha()
{
    int i = 0, j = 0;
    int flag = 0;
    for(i=0;i<3;i++)
    {
        if(flag)
        {
            cout << "Yes" << endl;
            return;
        }
        flag = 1;
        for(j=0;j<3;j++)
        {
            if(check[i][j] == 0)
            {
                flag = 0; break;
            }
        }
    }
    
    for(j=0;j<3;j++)
    {
        if(flag)
        {
            cout << "Yes" << endl;
            return;
        }
        flag = 1;
        for(i=0;i<3;i++)
        {
            if(check[i][j] == 0)
            {
                flag = 0; break;
            }
        }
    }
    if(flag)
        {
            cout << "Yes" << endl;
            return;
        }
        flag = 1;
    for(i=0;i<3;i++)
    {
        if(check[i][i] == 0)
            {
                flag = 0; break;
            }
    }
    if(flag)
        {
            cout << "Yes" << endl;
            return;
        }
        flag = 1;
    for(i=0;i<3;i++)
    {
        if(check[i][2-i] == 0)
            {
                flag = 0; break;
            }
    }
    if(flag)
        {
            cout << "Yes" << endl;
            return;
        }
    cout << "No" << endl;
            return;
}

int main()
{
   int n;
    map<int,pii> bingo;
    

    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            cin >> n;
            bingo.insert(make_pair(n,pii(i,j)));
            check[i][j] = 0;
        }
    
    int b;
    cin >> b;
    while(b--)
    {
        cin >> n;
        if(bingo.find(n) == bingo.end()) continue;
        check[bingo[n].first][bingo[n].second] = 1;
    }

    checalinha();
    


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;
 
ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}
ll mod(ll a, ll b) {return (a % b + b) % b;}
ll powerm(ll base,ll exp,ll mod) 
{ll ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
/*{{ x | (1 << k) sets the kth bit of x to one
x & ~(1 << k) sets the kth bit of x to zero
x ^ (1 << k) inverts the kth bit of x.
x & (x-1) sets the last one bit of x to zero
x & -x sets all the one bits to zero, except for the last one bit. 
x | (x-1) inverts all the bits after the last one bit.}} SOME BIT MANIPULATION*/
//__builtin_clz(x): the number of zeros at the beginning of the number
//__builtin_ctz(x): the number of zeros at the end of the number
//__builtin_popcount(x): the number of ones in the number
//__builtin_parity(x): the parity (even or odd) of the number of ones 
struct custom_hash 
{
    static uint64_t splitmix64(uint64_t x) 
	{
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const 
	{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
/*//DSU 
int parent[200005];
int rankr[200005];
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void make_set(int v) {
    parent[v] = v;
    rankr[v] = 0;
}
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rankr[a] < rankr[b])
            swap(a, b);
        parent[b] = a;
        if (rankr[a] == rankr[b])
            rankr[a]++;
    }
} */

int main()
{  
	fast; 
	ll n,k; cin>>n>>k;
	ll arr[n]; for(ll i = 0; i < n; i++) cin>>arr[i];
	ll i = k;
	ll j = 0;
	ll tries = n-k;
	while(tries--)
	{
		if(arr[i] > arr[j])
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
		i++;
		j++;
	}
	return 0;
}

Measured memory_bytes: 5208
#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
#define method(name,res,...) function<res (__VA_ARGS__) > name = [&](__VA_ARGS__) -> res
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
  ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
      if(b&1)res = res * x % MOD;
      x = x * x % MOD;
      b>>=1;
    }
    return res;
  }

  ll modinv(ll x){
    return modpow(x, MOD-2);
  }

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  void in(t&x){
    cin >> x;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

string reversed(string str){
  reverse(all(str));
  return str;
}

int npow(int n,int x){
  int res = 1;
  rep(i,x)res*=n;
  return res;
}


int func(int n){
  int res = INF;
  rep(i,1000){
    rep(j,1000){
      int m = n - npow(i,3) - npow(j,2);
      if(m>=0)chmin(res,i+j+m);
    }
  }
  return res;
}


int main(){
  int n;
  while(n=in()){
    cout << func(n) << endl;
  }
  return 0;
}



Measured memory_bytes: 3056
import heapq

n=int(input())
A=list(map(int, input().split()))
for i in range(n):
    A[i]=A[i]*(-1)
heapq.heapify(A)
ans=0
for i in range(n):
    a=heapq.heappop(A)
    if i==0:
        B=[a]
        heapq.heapify(B)
    else:
        b=heapq.heappop(B)
        ans=ans+b
        heapq.heappush(B, a)
        heapq.heappush(B, a)
print(-ans)


Measured memory_bytes: 102460
#include <cstdio>

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

int main(){
    int x,y,z;
    scanf("%d %d",&x,&y);
    if(x<y)z=gcd(x,y);
    else z=gcd(y,x);
    printf("%d\n",gcd(x,y));
    return 0;
}



Measured memory_bytes: 2736
//#include<bits/stdc++.h>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 0x3f3f3f3f
using namespace std;

int a[200005];
int main()
{
    ios::sync_with_stdio(false);
    ll m;
    cin>>m;
    ll ans=0;ll t=1;
    while(m!=1)
    {
        m/=2;
        ans+=t;
        t*=2;
    }
    cout<<ans+t<<endl;

    return 0;
}


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

int main() {
    int a,b,c,k;
    cin>>a>>b>>c;
    cin>>k;
    int ans=0;
    
    while(b<=a){
        b*=2;
        ans++;
    }

    while(b>=c){
        c*=2;
        ans++;
    }
 
    if(ans<=k) cout<<"Yes\n";
    else cout<<"No\n";
	return 0;
}


Measured memory_bytes: 3596
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()


Measured memory_bytes: 74388
using System;
public class Hello
{
    public static void Main()
    {
        int n=int.Parse(Console.ReadLine());
        int k = n / 2;
        if (n - (k * 2) != 0)
            k++;
        double a = (double)k / (double)n;
        Console.WriteLine(a);
    }
}

Measured memory_bytes: 13140
import java.util.Scanner;

class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int W = sc.nextInt();
    int H = sc.nextInt();
    int x = sc.nextInt();
    int y = sc.nextInt();
    int r = sc.nextInt();

    if(x < r || y < r || x+r > W || y+r > H){
      System.out.println("No");
    }else{
      System.out.println("Yes");
    }
  }
}



Measured memory_bytes: 26344
#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
#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--){
        string s;
        cin >> s;
        int flag = 0;
        for(int i = 0; i < (int)s.length(); i += 2){
            if(!(s[i] == 'h' and s[i + 1] == 'i')){
                flag = 1;
                break;
            }
        }
        if(flag){
            cout << "No\n";
        }else{
            cout << "Yes\n";
        }
    } 
}

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

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

int main(){
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int ans = (h2-h1)*60+(m2-m1)-k;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3636
k,n = map(int,input().split()) 
A=list(map(int,input().split()) )
ans=10**10
for i in range(len(A)):
    
    #時計回り　iからi-1に行く
    #0を超えない
    if A[i-1] - A[i] > 0:    
        dist1  = A[i-1] - A[i]    
    
    #0を超える
    else:
        dist1 = A[i-1] + (k-A[i])
    
        
    #反時計回り　i-1からiに行く
    
    if A[i] - A[i-1] < 0:    
        dist2  = A[i-1] - A[i]    
    
    #0を超える
    else:
        
        dist2 = A[i] + (k-A[i-1])
        
    dist = min(dist1,dist2)
    
    ans = min(ans,dist)

print(ans)   

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int h, w;

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

vector<string> s;

int bfs(int sx, int sy, int gx, int gy) {
    int d[w][h]; //スタート位置からの距離を持つ配列
    //配列を初期化しておく
    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < h; ++j) {
            d[i][j] = -1;
        }
    }

    queue<pair<int, int>> que;

    //スタート地点をキューに入れ、距離を0にする
    que.push(pair<int, int>(sx, sy));
    d[sx][sy] = 0;

    while (!que.empty()) {
        pair<int, int> p = que.front(); que.pop(); //キューの先頭を取り出す

        if (p.first == gx && p.second == gy) break; //取り出したものがゴールならば探索をやめる

        //4方向をループ
        for (int i = 0; i < 4; ++i) {
            //移動した後の点を(nx,ny)とする
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            //移動できる場所か判定
            if (0 <= nx && nx < w && 0 <= ny && ny < h && s[ny][nx] == '.' && d[nx][ny] == -1) {
                //移動できる場合はキューに入れて、その点の距離を設定
                que.push(pair<int, int>(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }

    int res = 0;

    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < h; ++j) {
            res = max(res, d[i][j]);
        }
    }

    return res;
}

int main() {

    cin >> h >> w;

    s.resize(h);
    for (int i = 0; i < h; ++i) {
        cin >> s[i];
    }

    vector<pair<int, int>> p;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (s[i][j] == '.') {
                p.push_back(make_pair(i,j));
            }
        }
    }

    int ans = 0;

    for (int i = 0; i < p.size()-1; ++i) {
        for (int j = i+1; j < p.size(); ++j) {
            ans = max(ans, bfs(p[i].second, p[i].first, p[j].second, p[j].first));
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll v[103],w[103];
ll ks(int n,int W){
  ll dp[W+1];
  memset(dp,0,sizeof(dp));  
  for(int i=0;i<n;i++) 
    for(int j=W;j>=w[i];j--)
      dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  return dp[W];
}


int main(){
  int n,W;
  cin>>n>>W;
  for(int i=0;i<n;i++)
     cin>>w[i]>>v[i];
  cout<<ks(n,W)<<endl;
 return 0; 
}


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

/*
int main(void){
	double x,y,v;
	int n,t;


	while(scanf("%lf",&v)!=EOF){
		
		t=(v/9.8);
		y=4.9*t*t;
		n=(y/5)+5;
		printf("%d\n",n);
		
	}
	
	return 0;
}
*/

int main(void){
	double x,y,v,t;
	int n,i;

	while(scanf("%lf",&v)!=EOF){
		for(i=1;;i++){
			t=sqrt((double)(5.0*(double)i-5.0)/4.9);
			//printf("i=%d %lf %lf\n",i,9.8*t,t);
			if((9.8*t)>=v){
				printf("%d\n",i);
				break;
			}
		}
	}
	
	return 0;
}
		
		

Measured memory_bytes: 628
#include <iostream>
#include <math.h>
#include <climits>
using namespace std;
#define int long long

int32_t main()
{
    int n;
    cin >> n;
    int k;
    cin >> k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin >> arr[i];
    }
    int dp[n];
    dp[0] = 0;
    dp[1] = abs(arr[1] - arr[0]);
    for(int i=2;i<n;i++)
    {
        int ans = INT_MAX;
        for(int j=1;j<=k;j++)
        {
            if(i-j>=0)
            ans = min(abs(arr[i]-arr[i-j])+dp[i-j],ans);
        }
        dp[i] = ans;
    }
    cout << dp[n-1] << endl;
}


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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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;
}

//グラフ関連
struct Edge {
    ll to, cap, rev;
    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    ll n, c;
    cin >> n >> c;
    vec<ll> a(n), b(n);
    REP(i, n) {
        cin >> a[i];
    }
    REP(i, n) {
        cin >> b[i];
    }

    vvec<ll> pow(410, vec<ll>(410, 1)); //a^c
    REP(i, 401) {
        REP(j, 401) {
            pow[i][j + 1] = pow[i][j] * i % MOD;
        }
    }

    vvec<ll> sum(410, vec<ll>(410, 0)); //a^c+..+b^c
    REP(i, 401) {
        REP(j, 401) {
            sum[i + 1][j] = (sum[i][j] + pow[i][j]) % MOD;
        }
    }

    vvec<ll> dp(n + 1, vec<ll>(c + 1, 0));
    dp[0][0] = 1;
    REP(i, n) {
        REP(j, c + 1) {
            REP(k, c - j + 1) {
                dp[i + 1][j + k] += (MOD + sum[b[i] + 1][k] - sum[a[i]][k]) % MOD * dp[i][j] % MOD;
                dp[i + 1][j + k] %= MOD;
            }
        }
    }
    cout << dp[n][c] << en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    while(t--)*/
    solve();

    return 0;
}


Measured memory_bytes: 7132
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair
#define eb emplace_back

const int MAX_N = 2e5+10;
int N;
ll x[MAX_N], y[MAX_N];

ll add(ll a, ll b)
{
	return a+b;
}

struct P {
	ll x, y;
	P(){}
	P(ll xx, ll yy) : x(xx), y(yy) {}
	
	P operator+(P p){
		return P(add(x, p.x), add(y, p.y));
	}
	
	P operator-(P p){
		return P(add(x,-p.x), add(y, -p.y));
	}
	
	P operator*(ll d){
		return P(x*d, y*d);
	}
	
	ll dot(P p){
		return add(x*p.x, y*p.y);
	}
	
	ll det(P p){
		return add(x*p.y, -y*p.x);
	}
};

P ps[MAX_N];

bool cmp_x(const P& p, const P& q)
{
	if(p.x != q.x) return p.x < q.x;
	return p.y < q.y;
}

vector<P> convex_hull(P* ps, int n)
{
	sort(ps, ps+n,cmp_x);
	int k = 0;
	vector<P> qs(n*2);
	for(int i=0;i<n;++i){
		while(k>1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
		qs[k++] = ps[i];
	}
	for(int i=n-2,t=k; i>=0; --i){
		while(k > t &&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
		qs[k++]=ps[i];
	}
	qs.resize(k-1);
	return qs;
}


ll dist(P p, P q)
{
	return abs(p.x-q.x)+abs(p.y-q.y);
}

void solve()
{
    set<pair<ll,ll>> points;
    for(int i=0;i<N;++i) points.emplace(x[i],y[i]);
    const int n = points.size();
	if(n <= 2){
		if(n == 1) cout<<0<<'\n';
		else{
			auto it = points.begin();
			auto p1 = *it;
			it++;
			auto p2 = *it;
			cout<< dist(P(p1.first,p1.second),P(p2.first,p2.second))<<'\n';
		}
	
	}else{
	    int sz=0;
	    for(auto p : points) ps[sz++]=P(p.first,p.second);
	    sort(ps,ps+n, cmp_x);
		vector<P> qs = convex_hull(ps, n);
		ll res = 0;
		const int m = qs.size();
		for(int i=0;i<m;++i)for(int j=i+1;j<m;++j)res=max(res, dist(qs[i],qs[j]));
		cout<<res<<'\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i=0;i<N;++i){
		cin >> x[i] >> y[i];
	}
	solve();
	return 0;
}

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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

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

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int main(){
    bool flag=false;
    ll ans=0,sum=0;

    int h,a;
    cin >>h>>a;

    //cout <<fixed<<setprecision(16)<< << endl;
    cout<< (h+a-1)/a <<endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MN 200005
#define LL long long
#define mp make_pair
#define fir first
#define sec second
#define pii pair<int,int>
inline void chkmax(int &a,int b){if(a<b)a=b;}
inline void chkmin(int &a,int b){if(a>b)a=b;}
inline int read(){
	   int a=0,fh=1;char c=getchar();
	   while(c>'9'||c<'0'){if(c=='-')fh=-1;c=getchar();}
	   while('0'<=c&&c<='9'){
		   a=a*10+c-48;
		   c=getchar();
	   }
	   return a*fh;
}
char ch[MN];
int main(){
	int n=read();
	LL ans=0;
	for(int i=1;i<=n;++i)
		if(i%3!=0&&i%5!=0)ans+=i;
	printf("%lld",ans);
	return 0;
}

















Measured memory_bytes: 3760
import collections

index = 0

def maxsushi(sushi_list,eaten_sushi):
    global index
    max_val = [0,0]
    for i in range(index,len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            index = i
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

Measured memory_bytes: 22620
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;cin>>a>>b>>c>>d;
  if(a+b>c+d) cout<<"Left"<<endl;
  else if(a+b==c+d) cout<<"Balanced"<<endl;
  else cout<<"Right"<<endl;
}

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

int main(){
  int N; cin >> N;
  for(int i=1; i<10; i++){
    for(int j=1; j<10; j++){
      if(N==i*j){
        cout << "Yes"; return 0;
      }
    }
  }
  cout << "No";
  return 0;
}

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

using namespace std;
mt19937_64 rng(58);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int x, n;
    cin >> x >> n;
    set<int> p;
    for (int i=0; i<n; i++) {
        int pi;
        cin >> pi;
        p.insert(pi);
    }
    int ans = -100;
    for (int i=-100; i<=200; i++) {
        if (p.count(i) > 0) continue;
        if (abs(i-x) < abs(ans-x)) {
            ans = i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n;i++)
#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,c;cin>>n>>m>>c;
  int ans=0;
  vector<int>b(m);
  for(int i=0;i<m;i++)
    cin>>b.at(i);
  for(int i=0;i<n;i++)
  {
    int sum=c;
    for(int j=0;j<m;j++)
    {
      int a;cin>>a;
      sum+=a*b.at(j);
    }
    if(sum>0)
      ans++;
  }
  cout<<ans;
}
      
      

Measured memory_bytes: 256
from itertools import permutations as perm
from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def yesno(v, yes="Yes", no="No", upper=False):
    if upper:
        print([yes.upper(), no.upper()][not v])
    else:
        print([yes, no][not v])


def is_prime(v):
    if v <= 1:
        return False
    for x in range(2, floor(v ** 0.5)):
        if v % x == 0:
            return False
    return True


def main():
    """エントリーポイント"""
    N = input(int)
    for x in range(N, 100003 + 1):
        if is_prime(x):
            print(x)
            break


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 3316
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>

void FuncA(){
	std::string s;
	std::cin >> s;
	if (s[0] == s[1] || s[0] == s[2] || s[1] == s[2]) {
		std::cout << "No" << std::endl;
	}
	else
	{
		std::cout << "Yes" << std::endl;
	}
}

int main()
{
	int A, B, K;
	std::set<int> s;
	std::cin >> A >> B >> K;
	int min = std::min(B + 1, A + K);
	for (int i = A; i < min; ++i) {
		s.insert(i);
	}
	int max = std::max(B - K + 1, A);
	for (int i = max; i < B + 1; ++i) {
		s.insert(i);
	}
	for (auto i : s) {
		std::cout << i << std::endl;
	}
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>

#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;
using ll = long long;

const ll mod = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  ll N, mini = LLONG_MAX;
  vector<ll> data(5);
  cin >> N;
  for(int i = 0; i < 5; i++) {
    cin >> data[i];
    if(data[i] < mini) {
      mini = data[i];
    }
  }
  cout <<  N / mini + bool(N % mini) + 4 << endl;
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut gone = std::collections::HashSet::new();
    gone.insert(1);
    let mut next = a[0];
    let mut ans = 1;

    loop {
        if next == 2 {
            echo!(ans);
            return;
        }

        if let Some(_) = gone.get(&next) {
            echo!(-1);
            return;
        }

        gone.insert(next);
        next = a[next - 1];
        ans += 1;
    }
}


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

using namespace std;

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


Measured memory_bytes: 256
def main():
    N = int(input())
    E = {}
    A = input()
    for _, a in enumerate(map(lambda i: int(i)-1, A.split(' '))):
        E[a] = E.get(a, 0) + 1

    for i in range(N):
        print(E.get(i, 0))

main()


Measured memory_bytes: 46468
#include<iostream>
using namespace std;
bool CheckT(int a,int b,int c);

int main(){
	int a,b,c,i,n;
	cin>>n;
	i=0;
	while(i<n){
		cin>>a>>b>>c;
		if(CheckT(a,b,c))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		a=b=c=0;
		i++;

	}
	return 0;
}

bool CheckT(int a,int b,int c){
	a*=a;
	b*=b;
	c*=c;
	if(a+b==c||b+c==a||a+c==b)return true;
	else return false;
}

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


int main() {
  string s,t;
  cin >> s >>t;
  int a=s.size();
  for(int i=0;i<a;i++){
      if(s[i]!=t[i]){cout << "No" << endl;
      return 0;}
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 3624
#!/usr/bin/env python3

LT = '<'
ADD = '+'

mc = 3
ops = []

zero = None
one = None
tp_size = 31
twopow = None

def getM():
    global mc
    mc += 1
    return mc - 1

def setOp(opc, i, j, k):
    ops.append(f'{opc} {i} {j} {k}')
    
def mylog(msg, *vs):
    ops.append(f"D '{msg}' " + ' '.join(map(str, vs)))

def assign(i, j):  # vec[i] <- vec[j]
    setOp(ADD, zero, j, i)

def add(i, j):
    m = getM()
    setOp(ADD, i, j, m)
    return m

def lt(i, j):
    m = getM()
    setOp(LT, i, j, m)
    return m

def le(i, j):  # vec[i] <= vec[j]
    m = lt(i, add(j, one))
    return m

def myor(i, j):
    return lt(zero, add(i, j))

def mynot(i):
    return lt(i, one)

def myand(i, j):
    m = mynot(myor(mynot(i), mynot(j)))
    # mylog('and', i, j, m);
    return m

# returns [vec[x], 2vec[x], 4vec[x], 8vec[x], ...]
def mktwopow(x):
    ret = []
    ret.append(x)
    last = x
    for k in range(1, tp_size):
        last = add(last, last)
        ret.append(last)
    return ret

def myifk(f, k): # if f > 0 then 2^k else 0
    if k == 0:
        return lt(zero, f)
    else:
        m = myifk(f, k-1)
        return add(m, m)

def myif(f, x): # if f > 0 then x else 0
    t = zero
    for k in range(tp_size - 1, -1, -1):
        s = myifk(myand(f, le(add(t, twopow[k]), x)), k)
        t = add(t, s)
    return t

def prod(x, y):
    t = zero
    s = zero
    for k in range(tp_size - 1, -1, -1):
        # mylog(f'k={k}', twopow[k])
        tc = add(t, twopow[k])
        f = le(tc, x)
        yf = myif(f, y)
        for i in range(k):
            yf = add(yf, yf)
        s = add(s, yf)
        t = add(t, myif(f, twopow[k]))
        # mylog('s', s)
        # mylog('t', t)
    return s
        
def pout():
    print(len(ops))
    for s in ops:
        print(s)                

def main():
    global ops, mc, zero, one, twopow
    ops = []
    zero = getM()
    one = lt(zero, add(lt(zero, 0), lt(zero, 1)))
    twopow = mktwopow(one)
    assign(2, prod(0, 1))
    pout()

main()


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

int main() {
    int a, b, c; cin >> a >> b >> c;
    cout << min(c,b/a) << endl;
}

Measured memory_bytes: 3572
#include <cstdio>

int checks(int A[], int t, int n) {
    int i;
    A[n] = t;
    for (i = 0; A[i] != t; i++);

    return i != n;
}

int main() {

    int i, n, q, t, A[10001], cnt;
    cnt = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &A[i]);

    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &t);
        if (checks(A, t, n)) cnt++;
    }
    printf("%d\n", cnt);
    
    
    return 0;
}


Measured memory_bytes: 2712
n = int(input())
l = []
for i in range(n):
    l.append(sorted(input()))
l.sort(key=len)
ans = []
for i in l[0]:
    for j in range(1, n):
        if i not in l[j]:
            break
        else:
            l[j].remove(i)
    else:
        ans.append(i)
print(*ans, sep="")

Measured memory_bytes: 9120
#include <iostream>
#include <string>

#define u unsigned
#define s short
#define ll long long
#define REP(i, a, b) for (auto i = (a); i < (b); i++)
#define REPR(i, a, b) for (auto i = (a-1); i >= (b); i--)

using namespace std;

int main()
{
    string S, T;
    cin >> S >> T;

    int len = S.length(), count = 0;
    REP(i, 0, len)
        if (S[i] != T[i])
            count++;

    cout << count << "\n";;
}

Measured memory_bytes: 3920
#include <iostream>
#include <cmath>
#include <string>
#include <utility>
using namespace std;
typedef long long int ll;

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

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

const ll INF = 1LL << 60;

int N, W, w[110], v[110];

// dp[i][w]:最初のi個の品物を容量w以下で持ち帰るときの価値の総和の最大値
ll dp[110][110000];

ll rec(int n, int wt) {
  if (n < 0) return 0;

  if (dp[n][wt] >= 0) return dp[n][wt];

  ll res;
  if (wt - w[n] < 0) res = rec(n-1, wt);
  else res = max(rec(n-1, wt-w[n]) + v[n], rec(n-1, wt));
  return dp[n][wt] = res;
}

int main() {
  cin >> N >> W;
  for (int i = 0; i < N; i++) cin >> w[i] >> v[i];

  for (int i = 0; i <= N; i++)
    for (int j = 0; j <= W; j++)
      dp[i][j] = -1;

  cout << rec(N, W) << endl;
  return 0;
}


Measured memory_bytes: 88192
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		int s = in.nextInt();
		int h = s / 3600;
		s -= h * 3600;
		int m = s / 60;
		s -= m * 60;
		out.printf("%d:%d:%d\n", h, m, s);
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}


Measured memory_bytes: 26540
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
const int MOD = 1000000007;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int bc(int n) { return n ? bc((n-1)&n)+1 : 0; }

int i, j, k, m, n, l;

int main() {
    cin >> n >> k;
    
    int g = 0;
    F0(i, n) {
        cin >> j;
        g = gcd(g, j);
        m = max(m, j);
    }
    
    if (m >= k && k % g == 0); else cout << "IM";
    cout << "POSSIBLE" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
//#pragma GCC optimize("Ofast")
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
//#define int ll
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX / 2;
const ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  ll N;
  cin >> N;
  vll A(N);
  rep(i, N) {
    cin >> A[i];
  }
  
  ll s = 0;
  ll temps = 0;
  rep(i, N){
    if(A[i] == 0) {
      s += temps / 2;
      temps = 0;
    } else {
      temps += A[i];
    }
  }
  s += temps / 2;
  
  fin(s);
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,ans=1;ll a[MAX],s;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	sort(&a[1],&a[n+1]);
	for(int i=1;i<=n;++i)a[i]+=a[i-1];
	for(int i=n-1;i;--i)
		if(a[i]*2>=a[i+1]-a[i])++ans;
		else break;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    long long N;
    long long A;

    scanf("%lld%lld", &N, &A);

    long long x[N+1];

    long long sum = 0;

    for(long long i = 1; i <= N; i++){
        scanf("%lld", &x[i]);
        sum += x[i];
    }

    long long dp[N+1][N+1][sum+1];

    for(long long j = 0; j <= N; j++){
        for(long long k = 0; k <= N; k++){
            for(long long s = 0; s <= sum; s++){
                if(j >= 1 && s < x[j]){
                    dp[j][k][s] = dp[j-1][k][s];
                }else if(j >= 1 && k >= 1 && s >= x[j]){
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]];
                }else if(j == 0 && k == 0 && s == 0){
                    dp[j][k][s] = 1;
                }else{
                    dp[j][k][s] = 0;
                }
            }
        }
    }

    long long ans = 0;

    long long max;

    if(sum/A < N){
        max = sum/A;
    }else{
        max = N;
    }

    for(long long k = 1; k <= max; k++){
        ans += dp[N][k][k*A];
    }

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

    return 0;
}

Measured memory_bytes: 52484
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
ll pow1(ll a, ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a;
		}
		a=a*a;
		b=b>>1;
	}
	return ans;
}
int ma = 0,h,w;
int vis[25][25];
char arr[25][25];
int dfs(int u, int v,int ans)
{
	int i;
	vis[u][v] = 1;
	pair<int,int> pr[4];
	pr[0] = mp(1,0);
	pr[1] = mp(-1,0);
	pr[2] = mp(0,-1);
	pr[3] = mp(0,1);
	queue<pair<int,pair<int,int> > > q;
	q.push(mp(u,mp(v,0)));
	// cout<<u<<" "<<v<<endl;
	// cout<<"_____________"<<endl;
	while(!q.empty())
	{
		pair<int,pair<int,int> > tp = q.front();
		q.pop();
		u = tp.f;
		v = tp.s.f;
		ans = tp.s.s;
		// cout<<u<<" "<<v<<endl;
		for(i=0;i<4;i++)
			if((u+pr[i].f)>=0 && (u+pr[i].f)<h && (v+pr[i].s)>=0 && (v+pr[i].s)<w && arr[u+pr[i].f][v+pr[i].s] == '.' && !vis[u+pr[i].f][v+pr[i].s])
			{
				vis[u+pr[i].f][v+pr[i].s] = 1;
				q.push(mp(u+pr[i].f,mp(v+pr[i].s,ans+1)));
			}
	}
	// cout<<"_____________"<<endl;
	return ans;
}
int main()
{
	int i,j,ans = 0;
	cin>>h>>w;
	for(i=0;i<h;i++)
		for(j=0;j<w;j++)
			cin>>arr[i][j];
	for(i=0;i<h;i++)
	{
		for(j=0;j<w;j++)
			if(arr[i][j] == '.')
			{
				memset(vis,0,sizeof(vis));
				ans = dfs(i,j,0);
				ma = max(ma,ans);
			}
	}
	cout<<ma<<endl;
	return 0;
}

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

using namespace std;

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

  int n;
  cin >> n;

  map<string, int> sm;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    sm[s] += 1;
  }

  int imax = 0;
  for (auto i : sm) {
    imax = max(i.second, imax);
  }

  for (auto i : sm) {
    if (i.second == imax) {
      cout << i.first << '\n';
    }
  }

  return 0;
}


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

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
	for (; first != last && first != --last; ++first)
		iter_swap(first, last);
}

int main() {
	string str;
	string str1, str2;
	string strA, strB, strC;
	int n;
	int a, b;
	getline(cin, str);
	n = str.length();
	a = (n - 1) / 2;
	b = (n + 3) / 2;
	str1 = str.substr(0, a);
	str2 = str.substr(b - 1, n - b + 1);
	strA = str1;
	strB = str2;
    strC = str;
	reverse(str1.begin(), str1.end());
	reverse(str2.begin(), str2.end());
    reverse(str.begin(), str.end());
	if (str1.compare(strA) == 0 && str2.compare(strB) == 0 && strC.compare(str) == 0) {
		printf("Yes");
	}
	else {
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 256