akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

int main() {
    int C[3][3];

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> C[i][j];
        }
    }

    int tmp = 0;
    for(int i = 1; i < 3; i++) {
        tmp = C[i][0] - C[0][0];
        for (int j = 1; j < 3; j++) {
            if(tmp != C[i][j] - C[0][j]) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    
    for(int i = 1; i < 3; i++) {
        tmp = C[0][i] - C[0][0];
        for (int j = 1; j < 3; j++) {
            if(tmp != C[j][i] - C[j][0]) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}

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

int main()
{
	int n,i;
	cin >> n;
	i = n ;
	int s = 0;
	while(i)
	{
		s += i%10 ;
		i /= 10 ;
	}
	if(n%s==0) cout << "Yes\n";
	else cout << "No\n" ;


}

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

int main() {
  int a;
  int b;
  int c;
  int d;
  
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  
  for (int i = 0; true;) {
    c = c - b;
    if (c <= 0) {
      cout << "Yes";
      return 0;
    }
    a = a - d;
    if (a <= 0) {
      cout << "No";
      return 0;
    }
  }
}

Measured memory_bytes: 3564
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string s,t;
 
int main(){
	cin >> s;
  	cin >> t;
   
  	sort(s.begin(),s.end());
  	sort(t.begin(),t.end());
  	
  	reverse(t.begin(),t.end());
  
  	if(s<t) cout << "Yes" << endl;
  	else cout << "No" << endl;
}

Measured memory_bytes: 384
n,k=map(int,input().split())
a=list(map(int,input().split()))
if k==0:
    ans=0
    for i in a:
        ans+=i^0
    print(ans)
    exit()
l=k.bit_length()-1
dp=[[0,0] for i in range(l+1)]
M=0
for i in a:
    if i>>l&1:
        dp[0][1]+=1<<l
    else:
        dp[0][0]+=1<<l
    M=max(M,i)
p=0
M=M.bit_length()
for i in range(l+1,M):
    for j in a:
        if j>>i&1:
            p+=1<<i
dp[0][0]+=p
dp[0][1]+=p
for i in range(l):
    b=[0,0]
    p=l-i-1
    for j in a:
        if j>>p&1:
            b[0]+=1
        else:
            b[1]+=1
    b[0]<<=p
    b[1]<<=p
    for smaller in range(1,-1,-1):
        if smaller:
            dp[i+1][1]=dp[i][1]+max(b)
        else:
            if k>>p&1:
                dp[i+1][1]=max(dp[i+1][1],dp[i][0]+b[0])
                dp[i+1][0]=dp[i][0]+b[1]
            else:
                dp[i+1][0]=dp[i][0]+b[0]
# print(dp)
print(max(dp[l]))


Measured memory_bytes: 14620
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef on_linux
	#include <sys/resource.h>
#endif

#ifdef dobby_is_a_free_elf
	#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
	#define trace(...) 0;
#endif

using namespace std;
using namespace __gnu_pbds;


#define all(x)                  (x).begin(), (x).end()
#define between(i,x,y)          ((i) >= (x) && (i) <= (y))
#define DECIMAL(n)              cout << fixed << setprecision(n)
#define fi                      first
#define lbd                     lower_bound
#define mem0(x)                 memset(x, 0, sizeof (x))
#define mem1(x)                 memset(x, -1, sizeof (x))
#define mp                      make_pair
#define pb                      push_back
#define pf                      push_front
#define ppb                     pop_back
#define ppf                     pop_front
#define sc                      second
#define sqr(a)                  ((a) * (a))
#define sz(x)                   (int)((x).size())
#define ubd                     upper_bound

#define int                     long long

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>,
      rb_tree_tag,
      tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0
// order_of_key(k) returns count of elements strictly smaller than k


const long double PI = 3.14159265358979323846264338;
const double eps = 1e-10;
#ifdef int
	const long long INF = 1e18;
#else
	const long long INF = 1e9;
#endif
const int32_t fftmod = 998244353;
const int32_t MOD = 1000000007;
const int32_t N = 1e5 + 10;
const int32_t NN = 1e6 + 10;

vector<pair<int, int32_t>> pf;
void factorize(int n)
{
	pf.clear();
	int cnt = 0;
	while (n % 2 == 0) {
		n = n / 2;
		cnt++;
	}
	if (cnt)
		pf.pb({2, cnt});
	for (int i = 3; i * i <= n; i += 2) {
		cnt = 0;
		while (n % i == 0) {
			cnt++;
			n /= i;
		}
		if (cnt)
			pf.pb({i, cnt});
	}
	if (n > 2)
		pf.pb({n, 1});
}

inline void elf_magic(int testcase)
{
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i < n; ++i) {
		factorize(i);
		int cnt = 1;
		for (auto [p, c] : pf) {
			cnt *= (c + 1);
		}
		ans += (cnt);
	}
	cout << ans;

	return;
}

int32_t main()
{
	#ifdef on_linux
	rlimit cpu_time {.rlim_cur = 2, .rlim_max = RLIM_INFINITY};
	setrlimit(RLIMIT_CPU, &cpu_time);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int TESTS = 1;
	//cin >> TESTS;
	for (int i = 1; i <= TESTS; ++i) {
		// cout << "Case #" << i << ": ";
		elf_magic(i);
		if (i != TESTS)	{ cout << '\n'; }
	}
	return 0;
}

Measured memory_bytes: 3652
parseInt(x) = parse(Int, x)

function main()
	s = map(parseInt, split(chomp(readline()), ""))
	k = parse(readline())
	x = 0
	for i in 1:length(s)
		if s[i] != 1
			print(s[i])
			break
		else
			x += 1
			if x==k
				print(1)
				break
			end
		end
	end
end

main()

Measured memory_bytes: 110984
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	
	int N;
	cin >> N;

	double ans = 0.0;
	for (int i = 0; i < N; ++i) {
		double x; string u;
		cin >> x >> u;
		if (u == "JPY") ans += x;
		else ans += x * 380000.0;
	}
	cout << ans << endl;




}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	A := nextInt()
	B := nextInt()
	C := nextInt()
	D := nextInt()

	fmt.Println(max(A*B, C*D))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}

func debug(args ...interface{}) {
	fmt.Fprintln(os.Stderr, args)
}


Measured memory_bytes: 1804
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = Integer.parseInt(sc.next());
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());

        int sum = 0;
        for (int i = 1; i < N + 1; i++) {

            int tmp = addPerDegit(i);

            if (A <= tmp && tmp <= B) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    private static int addPerDegit(int i) {
        int sum = 0;
        while (i > 0) {
            // 10の余りを足していく
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define rep(i,a,b) for(uint32 i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define ALL(x) (x).begin(),(x).end()

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;

template<typename T>
class hashmap64 {
	std::vector<std::pair<uint64, T>> map;
	uint64 mask, temp, count;
	uint64 hash64(uint64 key) {
		key = ~key;
		key ^= key << 13;
		key ^= key >> 19;
		return key ^ (key << 17);
	}
public:
	hashmap64() :map(8192, std::make_pair(~static_cast<std::uint_fast64_t>(0), T())) {
		mask = 8191; count = 0;
	}
	hashmap64(size_t s) {
		s |= s << 1;
		s |= s >> 2;
		s |= s >> 4;
		s |= s >> 8;
		s |= s >> 16;
		s |= s >> 32;
		mask = s;
		count = 0;
		map.resize(s + 1, std::make_pair(~static_cast<std::uint_fast64_t>(0), T()));
	}
	T &operator[](uint64 suf) {
		temp = mask&hash64(suf);
		while (map[temp].first != suf) {
			temp = mask&(temp + 1);
		}
		return map[temp].second;
	}
	void insert(uint64 key, const T &value) {
		temp = mask&hash64(key);
		while (~map[temp].first) {
			if (map[temp].first == key) {
				map[temp].second = value;
				return;
			}
			temp = mask&(temp + 1);
		}
		map[temp] = std::make_pair(key, value);
		++count;
		if ((count << 1) > mask) {
			std::pair<uint64, T> mkey;
			uint64 t = mask;
			mask = mask << 1 | 1;
			map.resize(mask + 1, std::make_pair(~static_cast<std::uint_fast64_t>(0), T()));
			while (~map[t].first) {
				--t;
			}
			while (++t <= (mask >> 1)) {
				mkey = map[t];
				map[t].first = ~static_cast<std::uint_fast64_t>(0);
				temp = mask&hash64(mkey.first);
				while (~map[temp].first) {
					temp = mask&(temp + 1);
				}
				map[temp] = mkey;
			}
			for (t = 0;t <= mask >> 1;++t) {
				if (~map[t].first) {
					mkey = map[t];
					map[t].first = ~static_cast<std::uint_fast64_t>(0);
					temp = mask&hash64(mkey.first);
					while (~map[temp].first) {
						temp = mask&(temp + 1);
					}
					map[temp] = mkey;
				}
			}
		}
		return;
	}
	bool find(uint64 key) {
		temp = mask&hash64(key);
		while (~map[temp].first) {
			if (map[temp].first == key) {
				return true;
			}
			temp = mask&(temp + 1);
		}
		return false;
	}
	bool empty(void) {
		return !count;
	}
	size_t size(void) {
		return count;
	}
};

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

	hashmap64<uint32> map(1);
	uint32 n;
	scanf("%u", &n);
	int64 a, sum = 1e15;
	uint32 ans = 0;
	map.insert(sum, 0);
	rep(i, 0, n) {
		scanf("%lld", &a);
		sum += a;
		if (map.find(sum)) {
			ans = std::max(ans, i + 1 - map[sum]);
		}
		else {
			map.insert(sum, i + 1);
		}
	}
	printf("%u\n", ans);
	return 0;
}

Measured memory_bytes: 15236
#include <bits/stdc++.h>
#define int long long
#define P(x) cout << x << endl
#define D(x) P(#x << ": " << x)
#define F(i,n) for (int i=0; i<(int)(n); i++)
#define DEC(i,n) for (int i=(int)(n); --i>=0;)
#define PB push_back
#define ALL(v) v.begin(), v.end()
using namespace std;

signed main() {
    int n; cin>>n;
    int a[n];
    F(i,n) cin>>a[i];
    int last_imp=0, sum=0;
    sort(a, a+n);
    F(i,n-1) {
        sum += a[i];
        if (a[i+1] > 2*sum)
            last_imp = i+1;
    }
    P(n-last_imp);
}

Measured memory_bytes: 1024
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A =list(map(int,input().split()))

    cash = 1000
    for i in range(N-1):
        if A[i+1]>=A[i]:
            stock = cash //A[i]
            cash += stock*(A[i+1]-A[i])

    print(cash)







if __name__ == "__main__":
    main()


Measured memory_bytes: 62120
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int A, B, C; cin >> A >> B >> C;
    if (A == B && A != C) cout << "Yes" << endl;
    else if (A == C && A != B) cout << "Yes" << endl;
    else if (B == C && B != A) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LOCAL 0
#define lli long long int
const int mod=(int)(1e8);
const lli pINF=(lli)(1e15);
const lli nINF=-LLONG_MAX;
void fast() {std::ios::sync_with_stdio(false);cin.tie(NULL);}
lli power(lli a,lli b){lli ans=1;while(b!=0){ if(b%2==1){ans*=a;}b/=2;a*=a;} return ans;}
lli invmod(lli a) {return pow(a,mod-2);}
#define vi vector<int>
#define vlli vector<lli>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int INT=1000000000;
const int INF=0x3f3f3f3f;
#define Pa pair<int,int>
#define si(n) scanf("%d",&n)
#define sli(n) scanf("%lld",&n)
#define printi(n) printf("%d\n",n)
#define ld long double
#define printli(n) printf("%lld\n",n)
#define all(v) v.begin(),v.end()
#define forn(i,n) for(int i=0;i<n;i++)
void print(int a[],int n){for(int i=0;i<n;i++) cout<<a[i]<<" ";}

int get(int x){
    int ans=0;
    while(x){
        ans+=(x%10);
        x/=10;
    }
    return ans;
}

int main() {
	int n;
	si(n);
	int ans=INT_MAX;
	
	for(int i=1;i<n;i++){
	    int f=i;
	    int s=n-i;
	    
	    ans=min(ans,get(f)+get(s));
	}
	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	int k;
	cin >> k;
	int l = s.size();
	set<string> se;
	for (char c = 'a'; c <= 'z'; c++) {
		for (int i = 0; i < l; i++) {
			if (s[i] == c) {
				string t;
				for (int j = i; j < l; j++) {
					t += s[j];
					se.insert(t);
					if (j - i + 1 >= k) {
						break;
					}
				}
			}
		}
		if (se.size() >= k) {
			break;
		}
	}
	auto itr = se.begin();
	for (int i = 0; i < k - 1; i++) {
		itr++;
	}
	cout << *itr << endl;
	return 0;
}

Measured memory_bytes: 3652
S = input()

def solve(S):
    mod = 10**9+7
    N = len(S)
    Aquest = []
    Cquest = []
    cntA,cntquest = 0,0
    for i in range(N):
        if S[i] in 'B?':
            Aquest.append([cntA,cntquest])
        if S[i]=='A':
            cntA += 1
        if S[i]=='?':
            cntquest += 1
    cntC,cntquest = 0,0
    for i in range(N-1,-1,-1):
        if S[i] in 'B?':
            Cquest.append([cntC,cntquest])
        if S[i]=='C':
            cntC += 1
        if S[i]=='?':
            cntquest += 1
    Cquest = Cquest[::-1]
    ans = 0
    for aquest,cquest in zip(Aquest,Cquest):
        a = aquest[0]*pow(3,aquest[1],mod)
        if aquest[1]>0:
            a += aquest[1]*pow(3,aquest[1]-1,mod)
        c = cquest[0]*pow(3,cquest[1],mod)
        if cquest[1]>0:
            c += cquest[1]*pow(3,cquest[1]-1,mod)
        ans += a*c%mod
    ans %= mod
    return ans
print(solve(S))

Measured memory_bytes: 65200
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a,b,c,k,ans=0;
	cin>>a>>b>>c>>k;
	if(k<=a){
		cout<<k<<"\n";
	}
	else if(k-a<=b){
		cout<<a<<"\n";
	}
	else{
		k=k-a-b;
		ans=ans+a-k;
		cout<<ans<<"\n";
	}
  return 0;
}

Measured memory_bytes: 3576
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        n: usize,
        s: [Bytes; n],
    }
    let mut l = 0;
    let mut m = vec![];
    let mut r = 0;
    for s in s {
        let mut v = vec![];
        for c in s {
            if c == b')' && v.last() == Some(&b'(') {
                v.pop();
            } else {
                v.push(c);
            }
        }
        match (v.first(), v.last()) {
            (Some(b'('), Some(b'(')) => l += v.len() as i64,
            (Some(b')'), Some(b'(')) => {
                let x = v.iter().filter(|&c| *c == b')').count() as i64;
                m.push((x, v.len() as i64 - x))
            }
            (Some(b')'), Some(b')')) => r += v.len() as i64,
            _ => {}
        }
    }
    m.sort_by_key(|m| m.0 - m.1);
    for m in m {
        if l >= m.0 {
            l -= m.0;
            l += m.1;
        } else {
            println!("No");
            return;
        }
    }
    if l == r {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 58556
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;

int main(){

    long long H,W,e,o,ans;
    
    cin >> H >> W;

    if(H==1||W==1){
        cout << 1;
        return 0;
    }

    ans = H*W/2;

    if(H%2==1
        && W%2==1){
            ans+=1;
        }


    cout << ans;



    return 0;
}

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

ll N;

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

  // vector<ll> v;
  // for (ll i = 1; i <= 13; i++) {
  //   v.push_back(i);
  // }
  // do {
  //   int ans = 0;
  //   for (int i = 1; i <= 13; i++) {
  //     ans += (i % v[i - 1]);
  //   }
  //   if (ans == 78) {
  //     for (auto &e : v) {
  //       cout << e << " ";
  //     }
  //     cout << endl;
  //   }
  // } while (next_permutation(v.begin(), v.end()));

  if (N == 1) {
    cout << 0 << endl;
  } else {
    cout << (N - 1) * N / 2 << endl;
  }

  return 0;
}

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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if((A==B) && (A!=C)) {
        cout << "Yes" << endl;
    } else if((A==C) && (A!=B)) {
        cout << "Yes" << endl;
    } else if((B==C) && (A!=B)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
def MI():
    return map(int, input().split())

n = int(input())

cnt=[0]*(n+1)
for i in range(n):
    a,b= MI()
    if a==b:
        cnt[i+1]=cnt[i]+1
    else:
        cnt[i+1]=0

if max(cnt)>2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 62552
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << std::setprecision(10) << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int l;
	std::cin >> l;
	double r=(double)l/(double)3;
	print(r*r*r);
	return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}


signed main(){
	int N;
	cin>>N;
	string S;cin>>S;
	int ans=1;
	rep(i,N-1)if(S[i+1]!=S[i])ans++;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

ll dp[105][110000];
int N;
ll W, w[105], v[105];


int main(void) {
  cin >> N >> W;
  rep(i, 1, N+1) cin >> w[i] >> v[i];
  
  ll w1 = w[1];
  if (w1>1000) {
    rep(i, 1, N+1) w[i] = w[i] - w1 + 1000;
  }
  
  for (int i=1; i<=N; i++) {
    for (int j=1; j<=105000; j++) {
      dp[i][j] = dp[i-1][j];
      if (j-w[i]>=0) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
    }
  }
  
  ll ans = 0;
  for (int wi=1; wi<=105000; wi++) {
    if (w1>1000 && (wi/1000)*w1+wi%1000>W) continue;
    if (w1<=1000 && wi>W) continue;
    
    ans = max(ans, dp[N][wi]);
    
  }
  
  cout << ans << endl;

    return 0;
}



Measured memory_bytes: 85984
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)


int main(){
	ll t;
	int n;
	cin>>t>>n;
	vector<ll> v;
	
	rep(i,n){
		ll a,b;
		cin>>a>>b;
		v.pb(a), v.pb(b);
	}
	
	int left = 0, right = 0;// (0,0)
	ll tmp = 0, ans = 0;

	while(left<=right){
		while( right+1<2*n && v[right+1] - v[left] <= t ){
			if((right+1)%2==1)tmp += v[right+1]-v[right];
			right++;
		}
		if(right%2==0)ans = max(ans,tmp+t-(v[right]-v[left]));
		else ans = max(ans,tmp);
		
		if(left%2==0)tmp -= v[left+1] - v[left];
		left++;
	}
	
	cout<<ans<<endl;
}

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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int w, a, b;
  cin >> w >> a >> b;
  cout << max(b-a-w, a-b-w, 0LL) << endl;

  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();    
        int N = r.i();
        int[] H = r.ii();
        boolean flag = true;
        for(int i = N-1; i > 0; i--){
            int d = H[i]-H[i-1];
            if(d >= 0)
                continue;
            else if(d == -1){
                H[i-1] = H[i];
            } else {
                flag = false;
                break;
            }                
        }
        println(flag ? "Yes" : "No");
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long.parseLong(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 43220
#include<iostream>
using namespace std;
int main()
{
    string a, b;
    cin >> a >> b;
    string s = a + b;
    int num = atoi(s.c_str());
    int max = 1000;
    string ans = "No";
    for(int i = 1; i < max; i++)
    {
        if(num == i*i)
        {
            ans = "Yes";
            break;
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
void main() {
	auto N = ri;
	auto S = rs.to!(dchar[]);
	debug S.writeln;
	ulong res;
	foreach(i; 0..N) {
		auto X = S.dup;
		auto a = X[0..i].sort().uniq.array;
		auto b = X[i..$].sort().uniq.array;
		debug writefln("%s %s", a, b);
		int tmp = setIntersection(a,  b).array.length.to!int;
		debug setIntersection(a, b).writeln;
		res = max(res, tmp);
	}
	res.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  vector<vector<int>> A(3);
  int a;
  REP(i, 3) {
    REP(j, 3) {
      cin >> a;
      A.at(i).push_back(a);
    }
  }
  int N;
  cin >> N;
  int b;
  REP(i, N) {
    cin >> b;
    REP(i, 3) {
      REP(j, 3) {
        if (A.at(i).at(j) == b) {
          A.at(i).at(j) = -1;
          break;
        }
      }
    }
    REP(i, 3) {
      if (A.at(i).at(0) == -1 && A.at(i).at(1) == -1 && A.at(i).at(2) == -1) {
        cout << "Yes" << endl;
        return 0;
      }

      if (A.at(0).at(i) == -1 && A.at(1).at(i) == -1 && A.at(2).at(i) == -1) {
        cout << "Yes" << endl;
        return 0;
      }
    }

    if ((A.at(0).at(0) == -1 && A.at(1).at(1) == -1 && A.at(2).at(2) == -1) ||
        (A.at(0).at(2) == -1 && A.at(1).at(1) == -1 && A.at(2).at(0) == -1)) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int d = sc.nextInt();
        int n = sc.nextInt();
        int ans = 0;

        if( n < 100 ){
           ans = (int)Math.pow(100.0 , (double)d) * n;
        }

        else{
            ans = (int)Math.pow(100.0 , (double) d) * 101;
        }

        System.out.println(ans);
        
    }
}

Measured memory_bytes: 21716
#include <stdio.h>
int partition(int A[],int p,int r);

int main(){
   int a[100000];
  int i,j,n;

  scanf("%d",&n);

  for(i=0;i<n;i++)

  scanf("%d",&a[i]);
  j=partition(a,0,n-1);
 
  for(i=0;i<j;i++)
 
  printf("%d ",a[i]);
  printf("[%d] ",a[j]);
  for(i=j+1;i<n-1;i++)
  
  printf("%d ",a[i]);
  printf("%d",a[i]);
  printf("\n");
  return 0;
}

int partition(int A[],int p,int r){ 
  int i,j,x,y;
  x=A[r];
  i=p-1;
  for(j=p;j<=r-1;j++){
    if(A[j]<=x){
      i=i+1;
      y=A[j];
      A[j]=A[i];
      A[i]=y;
    }
  }
    y=A[i+1];
    A[i+1]=A[r];
    A[r]=y;
  
  return i+1;
}


Measured memory_bytes: 2132
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        h: [usize; n],
        ab: [(usize, usize); m]
    }

    let mut good = vec![true; n];

    for (a, b) in ab {
        if h[a - 1] > h[b - 1] {
            good[b - 1] = false;
        } else if h[a - 1] < h[b - 1] {
            good[a - 1] = false;
        } else {
            good[b - 1] = false;
            good[a - 1] = false;
        }
    }
    let ans = good.iter().filter(|x| **x).count();

    println!("{}", ans);
}


Measured memory_bytes: 6676
use std::collections::HashSet;
use std::io::*;
use std::str::FromStr;

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

fn main() {
    let mut v = read::<usize>();
    let mut open = HashSet::<usize>::new();
    while !open.contains(&v) {
        open.insert(v);
        v = if v % 2 == 0 { v / 2 } else { v * 3 + 1 };
    }
    println!("{}", open.len() + 1);
}


Measured memory_bytes: 4352
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int P = 2019;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return a * b % P;
}
const int N = 2e5 + 100;
int n, s[N], bucket[N];
ll ans = 0;
char buf[N];
int main()
{
	scanf("%s", buf + 1);
	n = strlen(buf + 1);
	bucket[0] = 1;
	int pw = 1;
	for (int i = n; i >= 1; --i)
	{
		s[i] = add(s[i + 1], mul(pw, buf[i] - '0'));
		pw = mul(pw, 10);
		ans += bucket[s[i]];
		bucket[s[i]]++;
	}
	printf("%lld\n", ans); 
	return 0;
}


Measured memory_bytes: 4704
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
using ll = long long;
int main(){
    ll a, v, b, w, t, x ,c;
    cin >> a >> v >> b >> w >> t;
    x= v-w;
    c = labs(a-b);
    if(x*t < c){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
 ll h;
 cin >> h;
 int n=0;
 ll a=1;
 while(a<=h){
   a*=2;
   n++;
 }
 ll ans=1;
 rep(i,n-1){
   ans=ans*2+1;
 }
 cout << ans << endl;
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)




int main(){
    long long n,m;
    cin>>n>>m;
    vector<pair<long long,long long>> p(n);
    long long tmp=0;
    long long ans=0;
    rep(i,n){
        cin>>p[i].first>>p[i].second;
    }
    sort(p.begin(),p.end());
    rep(i,n){
        if(tmp+p[i].second<m){
            ans+=p[i].first*p[i].second;
            tmp+=p[i].second;
        }else{
            ans+=(m-tmp)*p[i].first;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;

}


Measured memory_bytes: 1792
N = gets.to_i
abc = (N-1).times.map { gets.split.map(&:to_i) }
Q, K = gets.split.map(&:to_i)
xy = Q.times.map { gets.split.map(&:to_i) }

e = Array.new(N+1) { {} }
abc.each do |a,b,c|
  e[a][b] = c
  e[b][a] = c
end

d = Array.new(N+1)
q = [[K, nil, 0]]
q.each do |i, prev, dist|
  e[i].keys.each do |n|
    next if n == prev
    d[n] = dist + e[i][n]
    q << [n, i, dist + e[i][n]]
  end
end

xy.each do |x,y|
  p d[x] + d[y]
end


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

using namespace std;

using ll = long long;
#define long long long

int main(void) {
    ll h, w;
    cin >> h >> w;
    vector<string> a(h);
    for(auto &l: a) cin >> l;

    vector<char> t(h), s(w);
    for(ll i=0; i<h; i++)
        for(ll j=0; j<w; j++)
            if(a[i][j] == '#')
                t[i] = s[j] = 1;

    for(ll i=0; i<h; i++, t[i] && (cout << endl))
        for(ll j=0; j<w; j++)
            if(t[i] && s[j])
                cout << a[i][j];
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=101;
int T[N];
int main()
{
	int n;
	cin>>n;
	long long ans=0;
	for(int i=1;i<=n;++i) cin>>T[i],ans+=T[i];
	int m;cin>>m;
	for(int i=1;i<=m;++i){
		int P,X;cin>>P>>X;
		printf("%lld\n",ans-T[P]+X);
	}
	return 0;
}


Measured memory_bytes: 256
#include "algorithm"
#include "iostream"
using namespace std;
int n, a[100001];
pair<int, int> x[100001];
int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> x[i].first;
            x[i].second = i;
        }
        sort(x, x + n);
        for (int i = 0; i < n; i++) {
            cout << x[i].second +1<< " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 1664
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N;
ll a[40]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main(){
    cin>>N;
    cout<<a[N-1];

    return 0;
}

Measured memory_bytes: 256
N, K = map(int,input().split())
x = list(map(int,input().split()))
if x.count(0):
    K -= 1
x_p = list(filter(lambda n:n>0,x))
x_n = list(filter(lambda n:n<0,x))
x_n = sorted(list(map(lambda n:n*(-1),x_n)))
ans = float('inf')
if K == 0:
    print(0)
    exit()
for i in range(K+1):
    p = i
    n = K-i
    if len(x_p) < p or len(x_n) < n:
        continue
    else:
        if p == 0:
            result = x_n[n-1]
        elif n == 0:
            result = x_p[p-1]
        else:
            if x_p[p-1] < x_n[n-1]:
                result = x_p[p-1]*2+x_n[n-1]
            else:
                result = x_p[p-1]+x_n[n-1]*2

    ans = min(ans, result)
print(ans)


Measured memory_bytes: 14252
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
string s,t;
set<int> se[30];
int main()
{
  cin >> s >> t;
  
  int ss = s.size(),ts = t.size();
  
  rep(i,26) se[i].clear();

  rep(i,ss) se[(int)(s[i]-'a')].insert(i);

  ll x = 0;
  int front = -1;
  bool f = true;
  
  rep(i,ts){
    int tn = t[i] - 'a';
    if(se[tn].empty()) {
      f = false;
      break;
    }
    auto itr = se[tn].upper_bound(front);
    if(itr!=se[tn].end()){
      front = *itr;
    }
    else{
      x++;
      front = *se[tn].begin();
    }
  }

  if(f){
    ll res = (ll)front+1+x*ss;
    cout << res << "\n";
  }
  else cout << -1 << "\n";
    
  return 0;
}


Measured memory_bytes: 5120
#include <stdio.h>

int main(void)
{
	int n;
	int data[11][11] = {0};
	int h, w;
	
	while (scanf("%d", &n)){
		if (n == 0){
			break;
		}
		
		for (h = 0; h < n; h++){
			for (w = 0; w < n; w++){
				scanf("%d", &data[h][w]);
				data[h][n] += data[h][w]; 
				data[n][w] += data[h][w];
			}
			data[n][n] += data[h][n];
		}
		for (h = 0; h <= n; h++){
			for (w = 0; w <= n; w++){
				printf("%5d", data[h][w]);
				data[h][w] = 0;
			}
			printf("\n");
		}
	}
	return (0);
}

Measured memory_bytes: 616
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
using namespace std;
typedef long long ll;

ll kek(ll a[],ll x,ll n){
	ll k0=0;
	ll k1=n/2;
	ll k2=n-1;
	if(a[0]>=x){
		return n;
	}
	if(a[n-1]<x){
		return 0;
	}
	while(a[k1+1]<x||a[k1]>=x){
		if(a[k1]>=x){
			k2=k1;
			k1=(k1+k0)/2;
		}
		else{
			k0=k1;
			k1=(k1+k2)/2;
		}
	}
	return (n-k1-1);
}
ll kek1(ll c[],ll x,ll n){
	ll k0=0;
	ll k1=n/2;
	ll k2=n-1;
	if(c[0]>x){
		return n;
	}
	if(c[n-1]<=x){
		return 0;
	}
	while(c[k1+1]<=x||c[k1]>x){
		if(c[k1]>x){
			k2=k1;
			k1=(k1+k0)/2;
		}
		else{
			k0=k1;
			k1=(k1+k2)/2;
		}
	}
	return (n-k1-1);
}
int main() {
	ll n;
	ll a[100009],b[100009],c[100009];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	for(int i=0;i<n;i++){
		cin>>c[i];
	}
	sort(a, a+n);
	sort(b,b+n);
	sort(c,c+n);
	ll ans=0;
	for(int i=0;i<n;i++){
		ans+=(n-kek(a,b[i],n))*kek1(c,b[i],n);
	}
	cout<<ans;
}

Measured memory_bytes: 2560
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static final int UNKNOWN = 0;
	static final int HONEST = 1;
	static final int DISKIND = 2;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int input[][] = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			int a = sc.nextInt();
			
			for(int j = 0; j < a; j++) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt();
				
				if(y == 1) {
					input[i][x] = HONEST;
				}
				else {
					input[i][x] = DISKIND;
				}
			}
		}
		
		int result = 0;
		//全探索
loop:		for(int i = 0; i < (int)Math.pow(2, n) ; i++) {
			//debug
//			System.out.println("PATTERN");
			int tmp = i;
			
			boolean isHonest[] = new boolean[n];
			
			for(int j = 0; j < n; j++) {
				if(tmp % 2 == 1) {
//					System.out.print("O ");
					isHonest[j] = true;
				}
				else {
//					System.out.print("X ");
					isHonest[j] = false;
				}
				
				tmp /= 2;
			}
//			System.out.println();
			
			int num = i;
			int honestNum = 0;
			
//			Arrays.fill(isHonest, true);
			for(int j = 0; j < n; j++) {
				for(int k = 0; k < n; k++) {
					
					if(isHonest[k] && input[k][j] == DISKIND) {
//						honestNum--;
//						System.out.println(k +" says "+j+" is diskind");
//						isHonest[k] = false;
						
						if(isHonest[j]) {
//							System.out.println("conflict!!");
							continue loop;
						}
					}
					
					if(isHonest[k] && input[k][j] == HONEST) {
//						honestNum--;
//						System.out.println(k +" says "+j+" is honest");
//						isHonest[k] = false;
						
						if(!isHonest[j]) {
//							System.out.println("conflict!!");
							continue loop;
						}
					}
//					else if(num%2 == 0 && input[k][j] == HONEST) {
//						System.out.println(k +" is diskind because of lying");
//						isHonest[k] = false;
//					}
//					else if(num%2 == 0 && j == k) {
//						honestNum--;
//						break;
//					}
				}
				
				num /= 2;
			}
			
			for(int j = 0; j < n; j++) {
				if(isHonest[j]) {
					honestNum++;
				}
			}
			
			result = Math.max(honestNum, result);
		}
		
		System.out.println(result);
	}

}


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

int main() {
  
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i=0; i<N; i++){
    cin >> a.at(i);
  }
  
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
      if(a.at(i)==a.at(j)){
        a.at(j)=0;
      }
    }
  }
  
  int k=0;
  for(int i=0; i<N; i++){
    if(a.at(i)!=0){
    k++;
    }
  }
  
  cout << k << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007

using namespace std;

int n,k;
int a[110];
int dp[110][100010];

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

	cin>>n>>k;
	for(int i=1;i<=n;i++)
        cin>>a[i];

    dp[0][0]=1;
    int suma;
    for(int i=1;i<=n;i++)
    {
        suma=0;
        for(int j=0;j<=k;j++)
        {
            suma=(suma+dp[i-1][j]-(j-a[i]-1>=0?dp[i-1][j-a[i]-1]:0))%mod;
            dp[i][j]=(suma+mod)%mod;
        }
    }
    cout<<dp[n][k];
	return 0;
}


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

int main(){
    int N;
    cin >> N;
    set<int> st;
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        st.insert(a);
    }
    cout << st.size() << endl;
    return 0;
}



Measured memory_bytes: 7756
n = int(input())
mod = 10**9+7

stone = [0 for _ in range(2*10**5)]
stone_last_pos = [-1 for _ in range(2*10**5)]

dp = [0 for _ in range(n+1)]
dp[0] = dp[-1] = 1

for i in range(n):
    c = int(input())
    if i == 0:
        dp[0] = 1
    else:
        p = stone_last_pos[c-1]
        if p == i-1:
            dp[i] = dp[i-1]
        elif p > -1:
            dp[i] = dp[i-1] + dp[p]
            dp[i] %= mod
        else:
            dp[i] = dp[i-1]
    stone_last_pos[c-1] = i

print(dp[n-1])


Measured memory_bytes: 57420
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define INF 10010
#define H 30
#define W 30
using namespace std;
using ll = long long;
using P = pair<int, int>;

int m[2*H-1][2*W-1];
int cost[2*H-1][2*W-1];

int bfs(int h, int w) {
  // Map is created;
  rep(i, 2*h-1)
    rep(j, 2*w-1)
      m[i][j] = -1;

  rep(i, 2*h-1){
    rep(j, w) {
      if (i % 2 == 0 && j == 0) continue;
      if (i % 2 == 0) {
        cin >> m[i][2*j-1];
      } else {
        cin >> m[i][2*j];
      }
    }
  }

  // Cost_Table is created;
  rep(i, 2*h-1)
    rep(j, 2*w-1)
      cost[i][j] = INF;

  cost[0][0] = 1;

  queue<P> q;
  q.push(P(0, 0));

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

  while(! q.empty()) {
    int xx, yy;
    yy = q.front().first; xx = q.front().second;
    q.pop();

    rep(i, 4) {
      int ny, nx;
      ny = yy + dy[i]; nx = xx + dx[i];

      if (ny < 0 || ny >= 2*h-1 || nx < 0 || nx >= 2*w-1) continue;
      if (m[ny][nx] == 1) continue;
      if (cost[ny+dy[i]][nx+dx[i]] != INF) continue;

      q.push(P(ny+dy[i], nx+dx[i]));
      cost[ny+dy[i]][nx+dx[i]] = cost[yy][xx] + 1;

      if (ny+dy[i] == 2*h-2 && nx+dx[i] == 2*w-2) {
        return cost[ny+dy[i]][nx+dx[i]];
      }
    }
  }

  return 0;
}

int main() {
  ll w, h;
  while(cin >> w >> h) {
    if (w == 0 && h == 0) break;
    cout << bfs(h, w) << endl;
  }

  return 0;

}



Measured memory_bytes: 3188
#include<cstdio>
#include<vector>
#include<map>
#include<string>

using namespace std;

int n;
char s[105];
vector<pair<string, int> > songs;

int main(){
	//freopen("IN","r",stdin);

	scanf("%d",&n);
	for(int i = 0; i < n;i++){
		int m;
		scanf("%s%d",s,&m);
		string name = s;
		songs.push_back({name,m});
	}
	scanf("%s",s);
	string name = s;
	int i = 0;
	for(;i < n;i++){
		if(songs[i].first == name) break;
	}
	i++;
	int res = 0;
	for(;i < n;i++){
		res += songs[i].second;
	}
	printf("%d\n", res);
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define int long long 
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	long long f=1,sum=0;
	char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=1000010;
char s[MAXN];
pa q[MAXN];
int h,t;
signed main()
{
	int n=read();
	scanf("%s",s+1);
	int qnum=read();
	for (int T=1;T<=qnum;T++)
	{
		h=t=0;
		int k=read(),dnum=0,sum=0,ans=0,mnum=0;
		for (int i=1;i<=n;i++)
		{
			if (s[i]=='C') ans+=sum;
			else if (s[i]=='M') sum+=dnum,mnum++;
			else if (s[i]=='D') dnum++;
			if (i-k+1>0)
			{
				if (s[i-k+1]=='D') sum-=mnum,dnum--;
				else if (s[i-k+1]=='M') mnum--;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;

int main(){
    int N;cin >> N;
    vector<LL> vec;
    int cnt  = 0;
    for(int i = 0;i < N;i++){
        int b;cin >> b;
        if(b < 0)cnt++;
        vec.push_back(abs(b));
    }
    if(cnt%2 == 0){
        cout<<accumulate(vec.begin(), vec.end(), 0LL)<<endl;
    }else{
        cout<<accumulate(vec.begin(), vec.end(), 0LL) - 2 * *min_element(vec.begin(),vec.end())<<endl;
    }
}


Measured memory_bytes: 1400
#include <algorithm>
#include <array>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <functional>
#include <queue>

//AtCoderC++.cpp

using namespace std;

void Show(vector<vector<int>> Ns) {
	for (int i = 0; i < Ns.size(); i++) {
		for (int j = 0; j < Ns[i].size(); j++) {
			if (j == Ns[i].size() - 1) {
				cout << Ns[i][j] << endl;
			} else {
				cout << Ns[i][j] << ",";
			}
		}
	}
}

void Show(vector<int> N) {
	for (int i = 0; i < N.size(); i++) {
		cout << N[i];
		if (i != N.size() - 1) {
			cout << " ";
		} else {
			cout << endl;
		}
	}
}


int main() {
	int A, B;
	cin >> A>> B;
	cout << (A + B) / 2 + (A + B) % 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	vector<string> vs;
	int n;
	cin>>n;
	map<string,int> mp;
	for(int i=0;i<n;i++)
	{
		string a
		;cin>>a;
		mp[a]++;
	}
	int sum = -1e5;
	for(map<string,int>::iterator it = mp.begin();it!=mp.end();it++)
	{
		if(it->second>sum)
		sum = it->second;
	}
	for(map<string,int>::iterator it = mp.begin();it!=mp.end();it++)
	{
		if(it->second == sum)
			cout<<it->first<<endl;
	}
	return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    ll Q,H,S,D,N;
    cin >>  Q  >> H >> S >> D >>  N;
    H = min(H,2*Q);
    S = min(S,2*H);
    ll ans;
    if(D > S*2){
        ans = N * S;
    }
    else{
        ans = (N/2)*D + (N%2)*S;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3600