akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll dp[2020][2020];

int main(){

    for(ll i = 0; i < 2020; i++){
        for(ll j = 0; j < 2020; j++){
            dp[i][j] = 1;
        }
    }

    ll N, M;
    cin >> N >> M;
    vector<ll>S(N + 1, -1), T(M + 1, -2);
    for(ll i = 1; i <= N; i++){
        cin >> S[i];
    }
    for(ll i = 1; i <= M; i++){
        cin >> T[i];
    }
    for(ll i = 1; i <= M; i++){
        for(ll j = 1; j <= N; j++){
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            dp[i][j] %= MOD;
            if(S[j] != T[i]){
                dp[i][j] = (dp[i][j] + MOD - dp[i - 1][j - 1]) % MOD;
            }
        }
    }
    cout << dp[M][N] << endl;

    return 0;
}

Measured memory_bytes: 32128
W, H=map(int,input().split())
arr = [input() for j in range(W)]
ans = ['' for i in range(W)] 

for i in range(0, W):
    for j in range(0, H):
        bomb_num = 0
        if arr[i][j] == '#':
            ans[i] += '#'
        else:
            for k in (-1, 0, 1):
                for l in (-1, 0, 1):
                    if (-1<i+k<W) and (-1<j+l<H):
                        if arr[i+k][j+l] == '#':
                            bomb_num += 1
                        
            ans[i] += str(bomb_num)
            
for i in range(W):
        print(ans[i])
        

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

#define ll long long
#define ull unsigned long long
#define LL long long
#define sl(n) scanf("%lld", &n)
#define sf(n) scanf("%lf", &n)
#define si(n) scanf("%d", &n)
#define sch(n) scanf(" %c", &n)
#define ss(n) scanf("%s", n)
#define pii pair <int, int>
#define pll pair <ll, ll>
#define plp pair <int, pll >
#define pb push_back
#define fr first
#define sc second
#define all(a)  a.begin(),a.end()
#define Unique(a)  sort(all(a)),a.erase(unique(all(a)),a.end())

#define inf (1LL<<50)
#define eps 1e-9

ll Set(ll n, ll pos)
{
    return n|(1LL<<pos);
}

bool Check(ll n, ll pos)
{
    return (bool) (n&(1LL<<pos));
}


vector <ll> ed[100050];

ll dp[100050];

ll solve(ll n)
{
   ll &ret = dp[n];
   if (ret != -1)
    return ret;
   ret = 0;
   for (ll i = 0; i < ed[n].size(); i++)
       ret = max(ret, solve(ed[n][i])+1);
   return ret;
}

int main ()
{
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    //  ios_base::sync_with_stdio(0); // no printf/scanf must be present
    ll cs, ts, i, j, k, x, y, z, q, m, n, cap;

    while(sl(n) != EOF)
    {
        sl(m);

        memset(dp, -1, sizeof(dp));

        for (i = 1; i <= n; i++)
            ed[i].clear();

        for (i = 1; i <= m; i++)
        {
            sl(x);
            sl(y);
            ed[x].pb(y);
        }
        ll ans = 0;
        for (i = 1; i <= n; i++)
            ans = max(ans, solve(i));
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 8576
#import math
#import itertools
#import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    b_sts=[False]*n
    for i in range(m):
        b=INT()
        b-=1
        b_sts[b]=True
        
    step=[0]*(n+2)
    step[1]=1
    for i in range(n):
        if b_sts[i]:
            continue
        else:
            step[i+2]=(step[i+1]+step[i])%MOD
    print(step[-1]%MOD)

if __name__=='__main__':
    do()

Measured memory_bytes: 13468
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1 LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    int N;cin >> N;
    int a = N /500;
    int b = N - a * 500;
    b = b / 5;

    cout << a * 1000 + b * 5 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[10000],b[10000];

int main()
{
	int n;
	long long c1=0,c2=0;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	for(int i=1; i<=n; i++)
		cin>>b[i];
	for(int i=1; i<=n; i++)
	{
		if(a[i]>b[i]) 
			c1=c1+a[i]-b[i];
		else if(a[i]<b[i]) 
		{
			if((b[i]-a[i])%2==0) 
				c2=c2+(b[i]-a[i])/2;
			else 
			{
				c1++;
				c2=c2+(b[i]-a[i]+1)/2;
			}
		}
	}

	if(c2>=c1) 
		cout<<"Yes"<<endl;
	else 
		cout<<"No"<<endl;
	return 0;
}

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

#define ll long long

#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define debug(x) cout<<#x<<": "<<x<<endl

#define ld double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define INF 1000000000000000000

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long double pi= 3.14159265358979323846;
    ll n,a,b;
    cin>>n>>a>>b;
    cout<<min(a,b)<<" "<<max(0ll,a+b-n);    
    return 0;
}

Measured memory_bytes: 256
N,K=map(int,input().split())

if K%2==0:
    X=int(2*N/K)
    if X%2==0:
        print(int((X**3)/4))
    else:
        print(int((X**3+X*3)/4))
else:
    print(int((int(N/K))**3))

Measured memory_bytes: 3060
n,m=map(int,input().split())
h=list(map(int,input().split()))
x=[1]*n
for i in range(m):
  a,b=map(int,input().split())
  A=h[a-1]
  B=h[b-1]
  if A!=B:
    z=min(A,B)
    if z==A:
       x[a-1]=0
    else:
       x[b-1]=0
  else:
    x[a-1]=0
    x[b-1]=0
  
print(sum(x))

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

int main(){
    int n;
    cin >> n;
    int l[11];
    int max = 0,j,sum = 0;
    for(int i=0;i<n;i++) cin >> l[i];
    for(int i=0;i<n;i++){
        if(max < l[i]){
            max = l[i];
            j = i;
        }
    }
    for(int i=0;i<j;i++){
        sum += l[i];
    }
    for(int i=j+1;i<n;i++){
        sum += l[i];
    }
    if(max < sum){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
$stdin = DATA if $stdin.eof?

target = gets.chomp.upcase

words = []

ARGF.each_line do |line|
  break if line =~ /^END_OF_TEXT$/
  words += line.split.map(&:upcase)
end

puts words.select{|e| e =~ %r/^#{target}$/ }.size

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

int main()
{
	int len, Q;	cin >> len >> Q;
	string s;	cin >> s;
	int sum = 0;
	vector <int> v(len);
	for (int i = 0; i < len-1; i++)
	{
		if (s[i] == 'A' && s[i + 1] == 'C')
		{
			v[i] = sum;
			v[i + 1] = ++sum;
		}
		else { v[i] = sum; v[i + 1] = sum; }
	}
	int start, end;
	for (int i = 0; i <	Q; i++)
	{
		cin >> start >> end;
		cout << v[end-1] - v[start-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1408
a,b = map(int,input().split())
c = [list(map(int,input().split())) for j in range(a)]
ans = 0
for l in range(a-1):
    for k in range(l+1,a):
        d = [(x-y)**2 for (x, y) in zip(c[l], c[k])]
        g = sum(d)
        s = g**0.5
        if s.is_integer():
            ans += 1
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {
		 
		static void solve() {
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
			int k = sc.nextInt();
			int res = 0;
			int array[] = new int[n];
			for(int i = 0;i<n;i++) {
				array[i] = sc.nextInt();
				if(array[i] >=k) {
					res++;
				}
			}
			System.out.println(res);
			sc.close();
		}
	public static void main(String[] args) {
			solve();

	}

}


Measured memory_bytes: 48520
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#include <bitset>
#define LL long long
 
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (c >= a && c <= b)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int x, a, b;
    cin >> x >> a >> b;

    int ans = x-a;

    int cnt = 0;
    while(true)
    {
        if(cnt * b <= ans)
        {
            cnt++;
        }
        else
        {
            cnt--;
            break;
        }
    }
    ans -= (cnt * b);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];

int solve(string s1,string s2){
	int m=s1.size() ;
	int n=s2.size() ;
	s1=' '+s1;
	s2=' '+s2;
	memset(dp,0,sizeof(dp));
	int maxl=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1]+1;
			else {
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
			maxl=max(maxl,dp[i][j]);
		}
	}
	return maxl;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		string s1,s2;
		cin>>s1>>s2;
		cout<<solve(s1,s2)<<endl;
	}
}


Measured memory_bytes: 7096
#include<stdio.h>
#define N 2000

int fanc1(int *, int, int, int,int);
int fanc2(int *, int, int, int, int);
int ruijou(int);
int kaijou(int);
int res(int, int);
void solv1(int A[], int mi, int n, int a);
  void solv2(int A[], int mi, int n, int a);

int j=0;
int main(){
  int n, q, a=0,i;
  int A[N],m[N],f;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++)
    scanf("%d",&m[i]);
    
  for(i=0;i<q;i++){
    f=fanc1(A,m[i],n,a,j);
    if(f==1)
      printf("yes\n");
    else{
 
      printf("no\n");
    }
  }

  return 0;
  
}
  

int fanc1(int A[], int mi, int n, int a, int i)
{

  int f, count,result;

  if(a==mi)
    return 1;
  if(i>=n){
      return 0;    
  }
  else{
    result=fanc1(A,mi,n,a,i+1)||fanc1(A,mi,n,a+A[i],i+1);
    return result;
  }
}

int fanc2(int A[], int mi, int n, int a, int i)
{

  int f, count,res;
  printf("%d\n",a);
  if(a==mi)
    return 1;
  if(i>=n){
      return 0;    
  }
  else{
    fanc1(A,mi,n,a,i+1);
    fanc2(A,mi,n,a+A[i],i+1);
  }
}

/*void solv1(int A[], int mi, int n, int a)
{
   fanc(A,mi,n,a);
   
}

void solv2(int A[], int mi, int n, int a)
{
 fanc(A,mi,n,a);
 
}
*/

int res(int n, int count)
{
  int b;
  b=ruijou(n+1);
  if(count>=b)
    return 0;
}

int kaijou(int n)
{
  if(n==0)
    return 1;
  else return n*kaijou(n-1);
  
}

int ruijou(int n)
{
  int i,a=1;
  for(i=0;i<n;i++){
    a= a*2;
  }
    return a;
}



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

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

using namespace std;
using ll = long long;

int main(void) {
  int n;
  cin >> n;
  int ans = 0;
  int num;
  rep(i, n) {
    cin >> num;
    ans += num - 1;
  }
  cout << ans << endl;
  return 0;
}



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

#define pb push_back
#define all(a) begin(a), end(a)
#define deb(x) cout << #x << " = " << x << endl
#define debu(x, y) cout << "( " << #x << ", " << #y << " ) = ( " << x << ", " << y << " )" << endl

typedef long long ll;
ll mod=1000000007;

const int N = 2e5 + 5;
vector<vector<int>> adj(N);
vector<bool> visited(N, false);
vector<int> ans(N, 1);
int val = 1;

void dfs(int i, int j) {
    if(visited[i]) return;
    visited[i] = true;
    for(auto u: adj[i]) {
        if(visited[u]) continue;
        dfs(u, i);
    }
    if(j == -1) return;
    ans[j] += ans[i];
    val = max(val, ans[j]);
}


template <typename T> vector<T> readVector(int n) { vector<T> res(n); for (int i = 0 ; i < n ; i++) cin >> res[i]; return res; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }

    //int ans = 0;

    for(int i=0; i<n; i++) {
        if(visited[i]) continue;
        dfs(i, -1);
        //ans = max(ans, ans[i]);
    }

    cout << val << endl;

    return 0;
}


Measured memory_bytes: 27480
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;

// Required random number generators

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
    #ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        //freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t clk;
    clk = clock();
//-----------------------------------------------------------------------------------------------------------//

    READV(N);
    ll ans=0;
    ll sub=0;
    FORI(i,0,N)
    {
        READV(X);
        ans+=X;
        ans%=MOD;
        sub-=((X*X)%MOD);
        sub+=MOD;
        sub%=MOD;
    }
    ans=(ans*ans)%MOD;
    ans=(ans+sub)%MOD;
    ans=(ans*modInverse(2))%MOD;
    cout<<ans<<endl;

//-----------------------------------------------------------------------------------------------------------//


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

    return 0;
}

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

int main (){
    int  H, W;
    while (1){
        cin >> H >> W;
        if ( H == 0 && W == 0 ) break;

        for (int i = 0; i < H; i++){
            for ( int j = 0; j < W; j++){
                cout  << "#";
            }
            cout << "\n";
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3128
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        BitSet bitSet = new BitSet(33554432);
        final char[] key = new char[128];
        key['A'] = 0;
        key['C'] = 1;
        key['G'] = 2;
        key['T'] = 3;
        for (int i = 0; i < n; i++) {
            String sp = bf.readLine();
            if (sp.charAt(0) == 'i') {
                int hash = 1;
                for (int j = 7; j < sp.length(); j++) {
                    hash <<= 2;
                    hash+=key[sp.charAt(j)];
                }
                bitSet.set(hash);
            } else {
                int hash = 1;
                for (int j = 5; j < sp.length(); j++) {
                    hash <<= 2;
                    hash+=key[sp.charAt(j)];
                }
                sb.append(bitSet.get(hash) ? "yes\n" : "no\n");
            }
        }
        bf.close();
        System.out.print(sb.toString());
    }
}


Measured memory_bytes: 69424
from sys import stdin
# from collections import defaultdict as dd
# from collections import deque as dq
# import itertools as it
# from math import sqrt, log, log2
# from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        l = i - intensity[i]
        r = i + intensity[i] + 1

        prefs[max(l, 0)] += 1
        if r <= n-1: 
            prefs[r] += -1
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    if sum(prefs) == n*n:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

Measured memory_bytes: 156596
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
 
int main(){
	
	ll a;
	double b;
	cin>>a>>b;
	ll c = (b+(1e-5))*100;
	cout << a*c/100 << endl;
	
	
}


Measured memory_bytes: 3696
#include<bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopb(i,a,b) for(int i=a;i>=b;i--)
#define loopm(i,a,b,step) for(int i=a;i<b;i+=step)
#define loopbm(i,a,b,step) for(int i=a;i>=b;i-=step)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define INF 1000000007
#define MOD 1000000007
#define BINF 1000000000000000001
#define int long long int
#define double long double

using namespace std;


#undef int
int main()
{
#define int long long int
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
 //   freopen("input.txt","r",stdin);
 int d;
 cin>>d;
 int n;
 cin>>n;
 
 if(d==0)
 {
 	if(n==100) cout<<101;
 	else cout<<n;
 }
 else if(d==1)
 {
 	if(n==100) cout<<10100;
 	else cout<<n*100;
 }
 else
 {
 	if(n==100) cout<<101*100*100;
 	else cout<<n*100*100;
 }
    return 0;
}

Measured memory_bytes: 256
s = input()

ans = 0
for i in range(len(s)):
    if i % 2 == 0 and s[i] == '0':
        ans += 1
    elif i % 2 == 1 and s[i] == '1':
        ans += 1

print(ans if ans < len(s)-ans else len(s)-ans)


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

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    reverse(A.begin(), A.end());
    vector<ll> sum(N+1), evensum(N+1);
    rep(i, N) {
        sum[i+1] = sum[i]+A[i];
        evensum[i+1] = evensum[i] + (i%2 == 0 ? A[i] : 0);
    }

    vector<ll> ths, vals;
    for (int k=0; k<(N-1)/2; ++k) {
        ll th = (A[k+1]+A[k*2+2])/2 + 1;
        ll val = sum[k+1] + evensum[N] - evensum[k*2+2];
        ths.push_back(th);
        vals.push_back(val);
    }
    reverse(ths.begin(), ths.end());
    reverse(vals.begin(), vals.end());
    rep(i, Q) {
        ll X;
        cin >> X;
        int index = upper_bound(ths.begin(), ths.end(), X) - ths.begin();
        if (index == 0) cout << sum[(N+1)/2] << endl;
        else cout << vals[index-1] << endl;
    }
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> L(N);

    for(int i = 0; i < N; i++){
        cin >> L.at(i);
    }

    sort(L.begin(),L.end());
    
    int ans = 0;

    for(int i = 0; i < N; i++){
        int a = L.at(i);
        for (int j = i+1; j < N; j++){
            int b = L.at(j);
            for (int k = j+1; k < N; k++){
                int c = L.at(k);
                if (c < a+b) ans++;
                else break;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define rep(i,x,n) for(int i=int(x);i<(int)(n);i++)


int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    rep(i, 0, n)cin >> a[i];
    sort(a.begin(), a.end());
    long long ans = 0;
    rep(i, 0, n)rep(j, i + 1, n) {
        long long bel = a[j] - a[i];
        long long bot = upper_bound(a.begin(), a.end(), bel) - a.begin();
        long long up = a[j] + a[i];
        long long top = lower_bound(a.begin(), a.end(), up) - a.begin();

        ans += (top - bot);
        if (a[i] > bel)ans--;
        if (a[j] > bel)ans--;
    }
    ans /= 3LL;
    cout << ans << endl;
}


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

template<typename T>
struct BinaryIndexedTree{
    vector<T> dat;
    BinaryIndexedTree(int n):dat(n+1,0){}
    void add(int i,T x){
        if (i==0) return;
        for (;i<=dat.size();i+=(i&-i)) dat[i]+=x;
    }
    T sum(int i){
        T res=0;
        for (;i>0;i-=(i&-i)) res+=dat[i];
        return res;
    }
    T query(int l,int r){ //[l,r)
        return sum(r-1)-sum(l-1);
    }
    int lower_bound(T x){
        if (x<=0) return 0;
        int lb=0,r=1;
        while(r<dat.size()) r<<=1;
        for (;r>0;r>>=1){
            if (lb+r<dat.size()&&dat[lb+r]<x){
                x-=dat[lb+r]; lb+=r;
            }
        }
        return lb+1;
    }
    void add0(int i,T x){add(i+1,x);}
    T sum0(int i){return sum(i+1);}
    T query0(int l,int r){return sum(r)-sum(l);}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,Q; cin >> N >> Q;
    vector<int> a(N);
    for (int i=0;i<N;++i) cin >> a[i];
    BinaryIndexedTree<long long> BIT(N);
    for (int i=0;i<N;++i) BIT.add0(i,a[i]);
    for (;Q--;){
        int t; cin >> t;
        if (!t){
            int p,x; cin >> p >> x;
            BIT.add0(p,x);
        } else {
            int l,r; cin >> l >> r;
            cout << BIT.query0(l,r) << '\n';
        }
    }
}

Measured memory_bytes: 10208
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace C_test_For_Atcorder
{
    public static class Extensions
    {
        public static string Reverse(this string sourse){
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }

    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.Read.Reverse();
			var words = new string[] { "maerd", "remaerd", "esare", "resare" };
            var flag = true;
            for (int i = 0; i < N.Length;)
            {
                var flag2 = false;
                foreach (var word in words)
                {
                    if (N.Length - i < word.Length) continue;
                    else if (N.Substring(i, word.Length) == word)
                    {
                        flag2 = true; i += word.Length;
                    }
                }
                if (!flag2) { flag = false; break; }
            }
            if (flag) WriteLine("YES");
            else WriteLine("NO");
        }
    }


    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue inputStream;

        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return (string)inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return (string)inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }

}


Measured memory_bytes: 13224
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; --i)
#define FOR(i, n, m) for (int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

typedef long long ll;
#define MAX 100005
#define NIL -1
/**
 * C問以降は ll を使う.
 * double型にするのを忘れない.
 * nC2の求め方 (1/2)*n*(n-1)
 * vector<型> 変数名(要素数, 初期値)
*/

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

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

void print(int u) {
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";

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

    cout << "[";

    for (int i = 0, c = T[u].l; c != NIL; i++, c = T[c].r) {
        if (i) cout << ", ";
        cout << c;
    }

    cout << "]" << endl;
}

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

int main() {
    int n;
    cin >> n;
    REP(i, n) {
        T[i].p = T[i].l = T[i].r = NIL;
    }
    int l;
    REP(i, n) {
        int v, d;
        cin >> v >> d;
        REP(j, d) {
            int c;
            cin >> c;
            if (j == 0) T[v].l = c;
            else T[l].r = c;
            l = c;
            T[c].p = v;
        }
    }

    int r;
    REP(i, n) {
        if (T[i].p == NIL) r = i;
    }

    rec(r, 0);

    REP(i, n) print(i);

    return 0;
}


Measured memory_bytes: 7688
#include<stdio.h>

int main(){
    int i,n,count=0;
    int p[20];
    
    scanf("%d",&n);
    for(i = 0; i < n; i++) scanf("%d",&p[i]);
    
    for(i = 1; i < n-1; i++){
        if(p[i-1] < p[i]){
            if(p[i] < p[i+1]) count++;
//            printf("%d is second\n",i);
        }
        if(p[i-1] > p[i]){
            if(p[i] > p[i+1]) count++;
//            printf("%d is second\n",i);
        }
    }
    printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 128
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define rep(i, n)           for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b)        for (int i = (int)(a); i < (int)(b); i++)
#define FOR(i, a)           for (auto &i : a)
#define ALL(obj)            begin(obj), end(obj)
#define MAX(x)              *max_element(ALL(x))
#define MIN(x)              *min_element(ALL(x))
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))
#define Endl                endl

using namespace std;
const int MOD    = (int)(1e9 + 7);
const int INF    = (int)(1e13 + 7);
const double EPS = 1e-14;
const double PI  = acos(-1);

int CEIL(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } //ceil() for int
int mod(int a, int b) { return a >= 0 ? a % b : a - (b * CEIL(a, b)); }             //always return positive num
int bpm(int x, int y) {                                                             //return x^y in order(log(y))
  if (x == 0) return 0;
  if (y == 0) return 1;
  int ans   = 1;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  x %= MOD;
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) ans = ans * x % MOD;
    x = x * x % MOD;
  }
  return ans;
}
template <class T>
struct trio {
  T first{};
  T second{};
  T third{};
};
template <class T>
void cumulative_sum(T &container) {
  for (int i = 0; i < container.size() - 1; i++) container[i + 1] += container[i];
}

class BPostdocs {
public:
  static void solve(istream &cin, ostream &cout) {
    string T;
    cin >> T;
    rep(i, T.size()) {
      if (T[i] == '?') T[i] = 'D';
    }
    cout << T << endl;
  }
};


signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  BPostdocs solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


Measured memory_bytes: 3772
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int BIG = 1e9;
const int maxN = 200 * 1000 + 9;
const string FILENAME = "sample";

ll n, k;
vector<pair<int, int> > edg;

void read(){
	cin >> n >> k;
}

void solv(){
	ll cur = (n - 1) * (n - 2) / 2;
	if(k > cur){
		cout << "-1\n";
		return;
	}
	
	for(int i = 2; i <= n; i++){
		edg.push_back(make_pair(1, i));
	}

	for(int i = 2; i <= n && cur > k; i++){
		for(int j = i + 1; j <= n && cur > k; j++){
			edg.push_back(make_pair(i, j));
			cur--;
		}
	}

	int m = edg.size();
	cout << m << '\n';
	for(int i = 0; i < m; i++){
		cout << edg[i].first << ' ' << edg[i].second << '\n';
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
#ifdef h4h4
	freopen((FILENAME + ".inp").c_str(), "r", stdin);
	freopen((FILENAME + ".out").c_str(), "w", stdout);
#endif

	read();
	solv();

	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <complex>
#include <regex>
#include <random>
using namespace std;

#define rep(i,n)	for(lint i = 0; i < n; i++)
#define repr(i,n)	for(lint i = n - 1; i >= 0; i--)
#define repi(i,ini,n)	for(lint i = ini; i < n; i++)
#define repir(i,ini,n)	for(lint i = n-1; i >= ini; i--)
#define repb(i,start,end)	for(lint i = start; i <= end; i++)
#define repbr(i,start,end)	for(lint i = end; i >= start; i--)

#define bit(n)				(1LL << (n))

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define rg(v, ini, end) v.begin() + ini, v.begin()+end

#define ret return 0;
#define chmax(a, b) a=mmax(a,b)
#define chmin(a, b) a=mmin(a,b)

using lint = long long;
using ulint = unsigned long long;
using ld = long double;
struct xy
{
	lint x, y;
	xy() :x(0), y(0) {}
	xy(lint _x, lint _y) : x(_x), y(_y) {}
	xy operator+(const xy& p) const
	{
		return xy(x + p.x, y + p.y);
	}
	bool operator<(xy p) const
	{
		if (y == p.y)
			return x < p.x;
		return y < p.y;
	}
};
struct xyd
{
	ld x, y;
	xyd() :x(0), y(0) {}
	xyd(long double _x, long double _y) : x(_x), y(_y) {}
};
using vec = vector<lint>;
using vecd = vector<ld>;
using vecs = vector<string>;
using vecp = vector<xy>;
template<class T> using vect = vector<T>;
class vec2 : public vector<vector<lint>>
{
public:
	vec2() {}
	vec2(lint n) : vector(n) {}
	vec2(lint h, lint w) : vector(h, vector<lint>(w)) {}
	vec2(lint h, lint w, lint v) : vector(h, vector<lint>(w, v)) {}
};

template<class T> using priq = priority_queue<T>;
template<class T> using rpriq = priority_queue<T, vector<T>, greater<T>>;
template<class Key, class Val> using hashmap = unordered_map<Key, Val>;
template<class Key> using hashset = unordered_set<Key>;

mt19937 mtrand((random_device())());

const double pi = 3.141592653589793238462;
const lint intmax = 9223372036854775807;
const lint inf = 1100100100100100100LL;

constexpr lint div2(lint p, lint q)
{
	return (p + q - 1) / q;
}

#if(__cplusplus < 201703L)

	lint gcd(lint a, lint b) {
		while (1) {
			if (a < b) swap(a, b);
			if (!b) break;
			a %= b;
		}
		return a;
	}

	lint lcm(lint a, lint b)
	{
		return a / gcd(a, b) * b;
	}

#endif

template<class T>
struct nval {
	lint n;		// counts
	T val;
	nval() : n(0) {};
	nval(lint _n, T _val) : n(_n), val(_val) {};
};

template<class It, class It2>
auto spacel(It i, It2 end)
{
	if (i + 1 == end)
	{
		return '\n';
	}
	else
	{
		return ' ';
	}
}

ostream& setp(ostream& ost)
{
	cout << setprecision(60) << fixed;
	return ost;
}

const ulint mod = 1000000007;
//const ulint mod = 998244353;
const ld eps = 0.0000001;

int main()
{
	while (1)
	{
		lint h, w;
		cin >> h >> w;
		if (h == 0 && w == 0)
			break;

		rep(i, h)
		{
			rep(j, w)
				cout << ((i + j) % 2 ? '.' : '#');
			cout << endl;
		}

		cout << endl;
	}

	return 0;
}



Measured memory_bytes: 3188
import numpy as np

H,W,K = list(map(int, input().split()))
t=[]
for i in range(H):
    t.append([int(i) for i in input().replace(".","0").replace("#","1")])

cnt = 0
for i in range(2**H):
    for j in range(2**W):
        d = np.array(t)
        i_2 = [int(k) for k in bin(i)[2:].rjust(H,"0")]
        j_2 = [ int(k) for k in bin(j)[2:].rjust(W,"0")]
        #print(i_2)
        #print(j_2)
        
        d= ((d.T)*i_2).T
        d= d*j_2
        
        num = d.sum()
        if num == K:
            cnt +=1
            
print(cnt)

Measured memory_bytes: 27200
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>
#include <bitset>

using namespace std;
typedef long long ll;

#define MAX_N 1000000
#define INF 1000000

int a[MAX_N];
int b[MAX_N];

bool kaibun(string s) {

  
  int n = s.size();
  int center;

  if (n%2==0) center = n/2;
  else center = (n-1)/2;
  
  for(int i = 0; i < center; i++){
    if (s[i] != s[n - 1- i]) {
      return false;
    }
  }
  return true;

}


int main() {

  // ---------------------
  // Input
  
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  string S;

  cin >> S;

  // ---------------------
  // 
  string sf = "";
  string sb = "";
  int n = S.size();
  int center = (n - 1)/2;
  
  for(int i = 0; i < center; i++){
    sf = sf + S[i];
    sb = S[n - 1 - i] + sb;
  }

  //cout << sf << endl;
  //cout << sb << endl;
  
  if( kaibun(S) && kaibun(sf) && kaibun(sb) ) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
  
}


Measured memory_bytes: 256
# n,k,*a=map(int,open(0).read().split())

# h = int(input())
h, k = [int(x) for x in input().split()]
# k = int(input())

# ヨコ
# m = [int(x) for x in input().split()]

# タテ
# m = [int(input()) for _ in range(N)]

if h < k:
  print(1)

elif h/k == h//k:
  print(h//k)

else:
  print(h//k+1)


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

cnt =0
for i in range(n-2):
    for j in range(i,n-1):
        for k in range(j,n):
            li = [l[i],l[j],l[k]]
            if len(set(li))==3 and max(li)*2<sum(li):
                cnt +=1
print(cnt)

Measured memory_bytes: 9184
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

    vector<int> es(n), ws(n);
    rep(i, n)
    {
        if (i == 0) {
            ws[i] = 0;
            es[n - 1 - i] = 0;
        } else {
            ws[i] = ws[i - 1] + (s[i - 1] == 'W' ? 1 : 0);
            es[n - 1 - i] = es[n - 1 - (i - 1)] + (s[n - 1 - (i - 1)] == 'E' ? 1 : 0);
        }
    }

    int result = numeric_limits<int>::max();
    rep(i, n)
    {
        result = min(result, ws[i] + es[i]);
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 3076
#include<stdio.h>
int main(){
  int i,n,x;
  fscanf(stdin,"%d",&n);
  for(i=1;i<=n;i++){
    x=i;
  if(x%3==0){
    printf(" %d",i);
    continue;
  }
  do{
  if(x%10==3){
    printf(" %d",i);
    break;
  }
  x/=10;
  }while(x);
  }
  printf("\n");
  return 0;
}


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

using namespace std;

using ll = long long;

int main(){
   ll n, a, b;
   cin >> n >> a >> b;
   for(ll i = a; i <= b; ++i){
    if(i % n == 0){
        cout << "OK";
        return 0;
    }
   }
   cout << "NG";
   return 0;
}


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

int main(){
    string s;
    string ans="";
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0') ans+='0';
        else if(s[i]=='1') ans+='1';
        else if(s[i]=='B'&&ans!="") ans.pop_back();
    }
    cout << ans << endl;
}

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

int main()
{
    ll r1,c1,r2,c2;
    cin >> r1 >> c1 >> r2 >> c2;
    const ll m = 1e9+7;
    ll n = r2+c2+2;

    auto mpow = [](ll x, ll y, ll m)
    {
        ll ret = 1;
        while(y!=0)
        {
            if(y&1) ret = (ret*x) % m;
            x = (x*x) % m;
            y = y >> 1;
        }
        return ret;
    };
    
    vector<ll> fac(n+1, 1); // n! % m
    vector<ll> finv(n+1, 1); // 1/k! % m = k!^(m-2) % m
    for(int i=0;i<n;++i)
    {
        fac[i+1] = (fac[i]*(i+1)) % m;
        finv[i+1] = (finv[i]*mpow(i+1, m-2, m)) % m;
    }

    auto mcomb = [&](ll r, ll c) {
        ll kf_inv = (finv[r-c]*finv[c]) % m;
        return (fac[r]*kf_inv) % m;
    };

    ll ans = mcomb(r2+c2+2,r2+1) - mcomb(r1+c2+1,r1) - mcomb(r2+c1+1,c1) + mcomb(r1+c1,r1);
    ans = (ans + 2*m) % m;
    
    cout << ans << endl;
    return 0;
}

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

using namespace std;
 
// Competetive Template:
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;

// Debugging :
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ba  back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair 
#define mt make_tuple
#define fi first
#define se second
#define gcd __gcd
#define maxe *max_element
#define mine *min_element
#define deb debug
 
#define forz(i,n) for(long long int i=0;i<n;i++)
#define rep(i,k,n) for (lli i = k; i <= n; i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)

typedef pair <lli,lli> pll;
 
// CODE BEGINS :

void solve()
{
    lli n, W; cin>>n>>W;
    lli w[n], v[n];

    forz(i,n) cin>>w[i]>>v[i];

    lli dp[n+1][W+1];

    forz(i,n+1)
    dp[i][0] = 0;

    forz(j,W+1)
    dp[0][j] = 0;

    for(lli i=1; i<=n; i++)
    {
        for(lli j=1; j<=W; j++)
        {
            lli t1=-1e17;

            if(j-w[i-1]>=0)
            t1 = dp[i-1][j-w[i-1]] + v[i-1];
            
            lli t2 = dp[i-1][j];

            dp[i][j] = fmax(t1, t2);
        }
    }

    cout<<dp[n][W];
}

int main()
{
    kira; 

    lli t=1; //cin>>t;

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




















Measured memory_bytes: 79232
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define reps(i,s,n) for(int (i) = (s); (i) < (n); ++(i))
#define rep(i,n) reps(i,0,n)
using ll = long long;
     
int main(){
	int x,a,b;
	cin >> x >> a >> b;

	if(a-b>=0) cout << "delicious" << endl;
	else if(b-a <= x) cout << "safe" << endl;
	else cout << "dangerous" << endl;
	
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
long long  n, x, a[110000], res;
int main(void){
    // Your code here!
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (a[0] > x) {
        res += a[0] - x;
        a[0] = x;
    }
    for (int i = 1; i < n; i++) {
        if (a[i - 1] + a[i] > x) {
            int t = a[i - 1] + a[i] - x;
            res += t;
            a[i] -= t;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] A;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        A = sc.nextIntArray(7);

        System.out.println(solve());
    }

    static long solve() {
        int I = A[0];
        int J = A[3];
        int L = A[4];

        if( I > 0 && J > 0 && L > 0 ) {
            return Math.max(use(I, J, L), notUse(I, J, L)) + A[1];

        } else {
            return notUse(I, J, L) + A[1];
        }
    }

    static long use(int i, int j, int l) {
        return notUse(i-1, j-1, l-1) + 3;
    }

    static long notUse(int i, int j, int l) {
        long ret = 0;
        ret += i/2*2;
        ret += j/2*2;
        ret += l/2*2;
        return ret;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 22740
#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>;

int main(){
    ll n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int max1 = 0, max2 = 0;
    rep(i, n){
        if (a[i] >= max1){
            max2 = max1;
            max1 = a[i];
        }
        else if (a[i] < max1 && a[i] > max2) max2 = a[i];
    }
    rep(i, n){
        if (a[i] == max1) cout << max2 <<endl;
        else cout << max1 <<endl;
    }
    return 0;
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int n;
	int a[101];
	int cost=10000000;
	int total=0;
	int x=101,y=-100;

	cin>>n;

	for(int i=1; i<n+1; i++){
		cin>>a[i];
		x=min(x,a[i]);
		y=max(y,a[i]);
	}
	for(int i=x; i<y+1; i++){
		total=0;
		for(int j=1; j<n+1; j++){
			total+=abs(i-a[j])*abs(i-a[j]);
		}
		cost=min(cost,total);
	}
	cout<<cost<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int q;
    cin >> q;

    while (q-- > 0) {
        long long a, b;
        cin >> a >> b;

        long long c = (long long) (sqrt(a * b - 1) + 0.5);
        if (c * c >= a * b) {
            --c;
        }
        long long res = 2 * c;
        if (c * (c + 1) >= a * b) {
            --res;
        }
        if (c >= a || c >= b) {
            --res;
        }
        
        cout << res << '\n';
    }

    return 0;
}

Measured memory_bytes: 256