akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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


ll f(ll n){
    if(n%2){
        return (n+1)/2%2;
    }else{
        return (n/2%2)^n;
    }
}

void solve() {
    ll A, B; cin >> A >> B;
    ll res = f(A-1)^f(B);

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(0)
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
typedef long long ll;
#define pri(n) printf("%d\n",n)
#define lpri(n) printf("%lld\n",n);
#define rep(i,st,ed) for(int i=st;i<ed;i++)
#define F first
#define S second 
#define pb(n) push_back(n)
const int N=1e5+6;
const ll M=1e9+7;

int main()
{
	string s,t;
	cin>>s>>t;
	s=' '+s;
	t=' '+t;
	int n=s.size();
	int m=t.size();

	int dp[n][m];
	memset(dp,0,sizeof(dp));

	for(int i=1;i<n;i++)
	{
		for(int j=1;j<m;j++)
		{
			if(s[i]==t[j])
				dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}

	string ans="";
	int row=n-1,col=m-1;

	while((int)ans.size()<dp[n-1][m-1])
	{
		int l=dp[row][col-1];
		int u=dp[row-1][col];
		int d=dp[row-1][col-1];
		int cur=dp[row][col];
		if(cur>l and cur>u and cur>d)
		{
			ans+=s[row];
			row--;
			col--;
		}		
		else
		{
			if(cur==l)
				col--;
			else row--;
		}

	}
	// cout<<"\t";
	// for(int i=0;i<m;i++)
	// 	cout<<t[i]<<' ';
	// cout<<"\n";
	// for(int i=0;i<n;i++)
	// {
	// 	cout<<s[i]<<"\t";
	// 	for(int j=0;j<m;j++)
	// 		cout<<dp[i][j]<<' ';
	// 	cout<<"\n";
	// }
	reverse(ans.begin(),ans.end());
	cout<<ans;


}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL -1
using namespace std;
const int64_t MOD = 1e9 + 7;

int main() {
	vector<int> a, b;
	a = { 1,3,5,7,8,10,12 };
	b = { 4,6,9,11 };

	int x, y;
	cin >> x >> y;

	int X, Y;
	if (count(a.begin(), a.end(), x)) X = 1;
	else if (count(b.begin(), b.end(), x)) X = 2;
	else X = 3;

	if (count(a.begin(), a.end(), y)) Y = 1;
	else if (count(b.begin(), b.end(), y)) Y = 2;
	else Y = 3;

	if (X == Y) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3628
import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
root=[[] for _ in range(n)]
f=lambda x:int(x)-1
 
for i in range(n-1):
  a,b=map(f,input().split())
  root[a].append(b)
  root[b].append(a)
 
score=[0]*n
for j in range(q):
  p,x=map(int,input().split())
  score[p-1]+=x
 
visit = [False]*n
def dfs(now):
  visit[now] = True
  for go in root[now]:
    if visit[go]:
      continue
    score[go] += score[now]
    dfs(go)

dfs(0)
print(*score)
  

Measured memory_bytes: 223276
#include<bits/stdc++.h>
using namespace std;
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define F first
#define S second
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define gcd __gcd
#define PI 3.141592653589
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
// Iterator
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define what(x) cerr << #x << " : " << x << "\n"
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define M 1000000007
#define N 100005  //check the limits, man
const ll INF = 1e18;
int cnt[N];
int bit[N];
void update(int j,int x)
{
    for(;j<N;j+=j&(-j))
        bit[j]+=x;
}
int query(int j)
{
    int x=0;
    for(;j>0;j-=(j)&(-j))
        x+=bit[j];
    return x;
}
int B;
int main()
{
    int n,m,l,r,i,j,k,a,b;
    in2(n,m);
    vector<triple> vp(n);
    rep(i,n)
    {
        in2(l,r);
        vp[i]=mt(r-l+1,l-1,r);
    }
    sort(all(vp));
    B=300;
    lp(j,1,B)
    {
        a=0;
        rep(i,n)
        {
            b=(tt(vp[i])/j)-(ts(vp[i])/j);
            if(b)
                a++;
        }
        cnt[j]=a;
    }
    i=0;
    while(i<n && tf(vp[i])<B)
        update(ts(vp[i])+1,1),update(tt(vp[i])+1,-1),i++;
    lp(j,B,m+1)
    {
        a=0;
        for(k=j;k<=m;k+=j)
            a+=query(k);
        cnt[j]=a+(n-i);
        while(i<n && tf(vp[i])<=j)
            update(ts(vp[i])+1,1),update(tt(vp[i])+1,-1),i++;
    }
    lp(j,1,m+1)
        out(cnt[j]);
}





Measured memory_bytes: 5248
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using vi = vector<int>;
using vv = vector<vi>;

int main(){
    string s; cin>>s;
    if(s[0]!='A')
      cout << "WA" << endl;
    else if(s[1]<'a')
      cout << "WA" << endl;
    else if(s.back()<'a')
      cout << "WA" << endl;
    else{
      int c = 0;
      for(int i=2; i<s.size()-1; i++){
        if(s[i]<'a' && s[i]!='C'){
          cout << "WA" << endl;
          return 0;
        }
        if(s[i]=='C')c++;
      }
      if(c==1)cout << "AC" << endl;
      else cout << "WA" << endl;
    }
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
using namespace std;

int main(){
	int m;
	double x,ans;
	cin >> m;
	for(int i=0;i<m;++i){
		cin >> x;
		ans += 1.0/x;
	}
	cout << 1.0/ans << endl;
    return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin>>N;
    --N;
    vector<int>arr(N);
    for(int i=0;i<N;i++)
        cin>>arr[i];
    // if(N==2){
    //     cout<<(arr[0]*2);
    //     return 0;
    // }
    long long total=0;    
    total+=(long long)arr[0];
    for(int i=0;i<N-1;i++){
        total+=(long long)min(arr[i],arr[i+1]);
    }
    total+=(long long)arr[N-1];
    cout<<total;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int sum = 0;
		int[] a = new int[N];
		for(int i=0;i<N;i++)a[i] = sc.nextInt();
		for(int i=0;i<N;i++){
			sum += a[i]-1;
		}
		System.out.println(sum);
	}
}

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

#define SIZE 10000000

int stack[SIZE];
int pos = 0;

int empty()
{
	return pos == SIZE;
}

void push(int x)
{
	if (empty())
		printf("ERROR\n");
	else
		stack[pos++] = x;
}

int pop()
{
	int x;

	if (pos == 0)
	{
		printf("ERROR\n");
		exit(1);
	}
	else
		x = stack[--pos];

	return x;
}

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void print(int A[], int N)
{
	int i;
	for (i = 0; i < N; i++)
	{
		if (i == N - 1)
			printf("%d\n", A[i]);
		else
			printf("%d ", A[i]);
	}
}

int main()
{
	int q;
	int num1, num2;
	int i, j;

	scanf("%d", &q);

	for (i = 0; i < q; i++)
	{
		scanf("%d", &num1);
		if (num1 == 0)
		{
			scanf("%d", &num2);
			push(num2);
		}
		else if (num1 == 1)
		{
			scanf("%d", &num2);
			printf("%d\n", stack[num2]);
		}
		else
		{
			pop();
		}
	}

	return 0;
}


Measured memory_bytes: 2568
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n, k;
llong h[100005];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    sort(h, h + n);

    llong ans = 1ll << 60ll;
    for (int i = k - 1; i < n; i++) {
        int j = i - (k - 1);

        ans = min(ans, llabs(h[i] - h[j]));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
M, K =map(int, input().split())
if K >= 2**M:
    ans = [-1]
elif M == 0:
    ans = [0, 0]
elif M == 1:
    if K == 1:
        ans = [-1]
    else:
        ans = [0, 0, 1, 1]
else:
    ans = list(range(K)) + list(range(K+1, 2**M)) +[K] + list(range(2**M-1, K, -1))+list(range(K-1, -1, -1)) +[K]
print(*ans)

Measured memory_bytes: 21104
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
 
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
	return r;
}

void solve()
{
	int n;
	cin >> n;
	set<string> st;
	rep(i, n){
		string s;
		cin >> s;
		st.insert(s);
	}
	cout << sz(st);
}


 // a b c a b c a b c a b c
 
int main()
{
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
    Red;
  	int T = 1;
  //	cin >> T;
  	for(int i = 1; i <= T; ++i){
  		solve();
  	}
  	return 0;

}

Measured memory_bytes: 19224
E=[[0 for j in range(4)]for i in range(2)]
while True:
  try:
    p =list(map(float,input().split()))
  except:
    break
  for i in range(2):
    if p[i]>=1.1:
      E[i][0]+=1
    elif p[i]>=0.6:
      E[i][1]+=1
    elif p[i]>=0.2:
      E[i][2]+=1
    else:
      E[i][3]+=1
      
for i in range(4):
  print(E[0][i], E[1][i])


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

const int N = 20005;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, x, t;


int main()
{
	cin >> n >> x >> t;
	x = ((n - 1) / x + 1) * t;
	cout << x << endl;
	return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void push(int);
int pop(void);

int top,S[1000];

int main(){
  int x,y;
  top=0;
  char s[100];
  while(scanf("%s",s)!=EOF){
    if(s[0]=='+'){
      x=pop();
      y=pop();
      push(x+y);
    }
    else if(s[0]=='-'){
      y=pop();
      x=pop();
      push(x-y);
    }
    else if(s[0]=='*'){
      x=pop();
      y=pop();
      push(x*y);
    }
    else {
      push(atoi(s));
    }
  }
  printf("%d",pop());
  printf("\n");
  return 0;
}

void push(int a){
  S[++top]=a;
}

int pop(void){
  top--;
  return S[top+1];
}


Measured memory_bytes: 2104
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了：sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    S = input()

    while 1:
        if S == '':
            print('YES')
            sys.exit()
        elif end_match('dreamer', S):
            S = S[:-7]
            # print('a', S)
        elif end_match('eraser', S):
            S = S[:-6]
            # print('b', S)
        elif end_match('dream', S):
            S = S[:-5]
            # print('c', S)
        elif end_match('erase', S):
            S = S[:-5]
            # print('d', S)
        else:
            print('NO')
            sys.exit()

def end_match(query, S):
    length = len(query)
    end = S[-length:]
    # print(query, end)
    if end == query:
        return True
    else:
        return False

if __name__ == "__main__":
    main()

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

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<int>> cond(Q, vector<int>(4));

    for (int i = 0; i < Q; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> cond.at(i).at(j);
        }
    }

    vector<int> A(10);
    int ans = 0, ans_max = 0;
    for (int i1 = 1; i1 <= M; i1++) {
        for (int i2 = i1; i2 <= M; i2++) {
            for (int i3 = i2; i3 <= M; i3++) {
                for (int i4 = i3; i4 <= M; i4++) {
                    for (int i5 = i4; i5 <= M; i5++) {
                        for (int i6 = i5; i6 <= M; i6++) {
                            for (int i7 = i6; i7 <= M; i7++) {
                                for (int i8 = i7; i8 <= M; i8++) {
                                    for (int i9 = i8; i9 <= M; i9++) {
                                        for (int i10 = i9; i10 <= M; i10++) {
                                            A = {i1, i2, i3, i4, i5, i6, i7, i8, i9, i10};
                                            for (vector<int> c: cond) {
                                                // cout << c.at(3);
                                                if (A.at(c.at(1) - 1) - A.at(c.at(0) - 1) == c.at(2)) {
                                                    ans += c.at(3);
                                                }
                                            }
                                            ans_max = max(ans, ans_max);
                                            ans = 0;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans_max << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <sstream>
#include <string.h>

using namespace std;

void solve()
{
	bool isPalinNum[10010];
	memset(isPalinNum, 0, sizeof(isPalinNum));
	for(int i = 1; i < 10010; ++i)
	{
		stringstream ss;
		ss << i;
		bool flag = true;
		string s = ss.str();
		for(int j = 0; j < s.size() / 2; ++j)
		{
			if(s[j] != s[s.size() - j - 1])
			{
				flag = false;
				break;
			}
		}
		if(flag)
		{
			isPalinNum[i] = true;
		}
	}
	int n;
	cin >> n;
	if(isPalinNum[n])
	{
		cout << n << endl;
	}
	else
	{
		int ans_cand[2] = {0};
		for(int i = n - 1; i >= 0; --i)
		{
			if(isPalinNum[i])
			{
				ans_cand[0] = i;
				break;
			}
		}
		for(int i = n + 1; i < 10010; ++i)
		{
			if(isPalinNum[i])
			{
				ans_cand[1] = i;
				break;
			}
		}
		if(n - ans_cand[0] <= ans_cand[1] - n)
		{
			cout << ans_cand[0] << endl;
		}
		else
		{
			cout << ans_cand[1] << endl;
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1236
c = []
for i in range(3):
    c.append(list(map(int, input().split())))
for i in range(2):
    for j in range(2):
        x = c[i][j] - c[i][j+1]
        y = c[i+1][j] - c[i+1][j+1]
        if x != y:
            print("No")
            exit(0)
print("Yes")


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>

using namespace std;

struct arena{
  int Aindex;
  int Bindex;
};

int main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  arena arr[M + 1];
  bool used[N + 1] = {false};
  int prevA = N / 2, prevB = N / 2 + 1;
  if (N & 1)
    for (int i = 1; i <= M; i++)
      arr[i] = {prevA - i + 1, prevB + i - 1};
  else{
    for (int i = 1; i <= (M + 1) / 2; i++)
      arr[i] = {i, N + 1 - i};
    for (int i = (M + 1) / 2 + 1; i <= M; i++)
      arr[i] = {i, N - i};
  }
  for (int i = 1; i <= M; i++)
    cout << arr[i].Aindex << ' ' << arr[i].Bindex << '\n';
  return 0;
}


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

int main() {
  int N, M;
  cin >> N >> M;
  vector<P> p(M);
  for(int i = 0; i < M; i++){
    cin >> p[i].first >> p[i].second;
  }
  for(int x = 0; x < 1000; x++){
    int keta = 1;
    int nx = x/10;
    vector<int> d(1,x%10);
    while(nx){
      keta++;
      d.push_back(nx%10);
      nx = nx/10;
    }
    if(keta != N) continue;
    bool ok = true;
    reverse(d.begin(), d.end());
    for(int i = 0; i < M; i++){
      if(d[p[i].first-1] != p[i].second) ok = false;
    }
    if(ok){
      cout  << x << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
//#define TEST


int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\stdout", "w", stdout);
    }

    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    FOR(i, N)
        cin >> A[i];
    vector<int> B(M), C(M);
    vector<pii> CB;
    FOR(i, M) {
        cin >> B[i] >> C[i];
        CB.push_back(make_pair(C[i], B[i]));
    }
    sort(CB.begin(), CB.end());
    sort(A.begin(), A.end());

    ll sol = 0;
    int j = CB.size()-1;
    FOR(i, N){
        if (j>=0 && CB[j].first > A[i]){
            sol += CB[j].first;
            CB[j].second--;
            if (CB[j].second == 0)
                j--;
        }
        else{
            sol += A[i];
        }
    }
    cout << sol << '\n';
    if (argc == 2 && atoi(argv[1]) == 123456789)
        cerr << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}


Measured memory_bytes: 2552
#include<bits/stdc++.h>
using namespace std;
vector <int> adj[100005];


int main()
{
    string s, t;
    cin>>s>>t;
    int ls, lt;
    ls = s.length();
    lt = t.length();
    
    int dp[ls+1][lt+1];
    memset (dp, 0, sizeof(dp));
        
    for (int i = 1; i<=ls; i++)
    {
        for (int j = 1; j<=lt; j++)
        {
            if (s[i-1]==t[j-1])
                dp[i][j] = 1+dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
        }
    }
    
    int ind = dp[ls][lt];
    char str[ind+5];
    str[ind]='\0';
    
    int i = ls, j = lt;
    while (i>0 && j>0)
    {
        if (s[i-1]==t[j-1])
        {
            str[ind-1] = s[i-1];
            ind--;
            i--;
            j--;
        }
        else if (dp[i-1][j]>dp[i][j-1])
            i--;
        else
            j--;
    }
    cout<<str;
    
    
    return 0;
}


Measured memory_bytes: 37760
<?php
$input = trim(fgets(STDIN));
if ($input < 111 || $input > 999 ) {
    exit(1);
}
$length = strlen($input);
for($i=0;$i<$length;$i++) {
    $n = substr($input, $i, 1);
    $map = [1 => 9, 9 => 1];
    if (isset($map[$n])) {
        $n = $map[$n];
    }
    echo $n;
}

Measured memory_bytes: 3828
#include <stdio.h>
#include <stdlib.h>

int main(void){
	int A, B, C, X;
	int total;
	int count;
	int i, j, k;

	scanf("%d %d %d %d", &A, &B, &C, &X);
	count = 0;
	i = 0;
	while (i <= A){
		j = 0;
		while (j <= B){
			k = 0;
			while (k <= C){
				total = 500*i + 100*j + 50*k;
				if (total == X){
					count++;
				}
				k++;
			}
			j++;
		}
		i++;
	}
	printf("%d\n", count);
	return (0);
}


Measured memory_bytes: 1728
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
  double r,pai,s,l;
  pai=3.141592653589;
  cin>>r;
  s=r*r*pai;
  l=2*r*pai;
  printf("%f %f\n",s,l);
  return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

int main(void) {
  string W, T;
  string item;
  string t;
  int cnt = 0;
  cin >> W;
  cin.ignore();
  while(getline(cin, T) && T != "END_OF_TEXT") {
    transform(T.begin(), T.end(), T.begin(), ::tolower);
    stringstream ss(T);
    while(getline(ss, item, ' '))
      if(item == W)
        cnt++;
  }
  cout << cnt << endl;
  return 0;
}

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

#define ll long long int
int main()
{
    ll n,p,q,x,y,i,k,a,b;

    cin>>n>>k;
    ll ara[n];
    for(i=0;i<n;i++) cin>>ara[i];

    if(k==0){
        cout<<*max_element(ara,ara+n)<<endl;
        return 0;
    }

    ll mx= 1e18+100;

    ll l=1, r=mx;
    bool bl=false;

    while(l<=r){
        ll mid=(l+r)/2ll;
        ll tot=0;

        for(i=0;i<n;i++){
            ll x=(ara[i]-1)/mid;
            tot+=x;
        }


        if(tot<=k) mx=min(mx, mid), r=mid-1;
        else l=mid+1;

    }

    cout<<mx<<'\n';
}


Measured memory_bytes: 5052
s = input()
n = len(s)
if s[0] == s[1]:
  print(1,2)
  exit()
for i in range(2,n):
  if s[i] == s[i-1]:
    print(i,i+1)
    exit()
  elif s[i] == s[i-2]:
    print(i-1,i+1)
    exit()
print(-1,-1)

Measured memory_bytes: 3188
#include<stdio.h>
#include<string.h>
#define int long long
char s[1000000];
int l,cnt,ans;
signed main(){
	scanf("%s", &s);
	l=strlen(s);
	for(int i=0;i<l;i++){
		if(s[i]=='A') cnt++;
		else if(s[i]=='B'&&s[i+1]=='C'){
			i++;
			ans+=cnt;
		}else cnt=0;
	}
	printf("%lld", ans);
}


Measured memory_bytes: 384
S = input()
a = int(S[0:2])
b = int(S[2:4])
if 1<=a<=12:
    if 1<=b<=12:
        print('AMBIGUOUS')
    else:
        print('MMYY')
elif 1<=b<=12:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 38384
n = int(input())
a = list(map(int, input().split())) + [-1]

money = 1000
k = 0

for i in range(n):
    if a[i+1] > a[i]:
        k += money//a[i]
        money = money - a[i]*(money//a[i])
    elif a[i+1] <= a[i]:
        money += k*a[i]
        k = 0

print(money)
    

Measured memory_bytes: 61908
const MOD = Int64(10^9 + 7)

function main()
  n, m = map(s -> parse(Int64, s), split(readline()))
  answer = Int64(1)
  i = Int64(2)

  while i * i <= m
    if m % i == 0
      count = Int64(0)
      while m % i == 0
        count += 1
        m /= i
      end
      answer *= comb(n + count - 1, count)
      answer %= MOD
    end
    i += 1
  end

  if m > 1
    answer *= n
    answer %= MOD
  end

  println(answer)
end

function comb(n::Integer, k::Integer)
  if n - k < k return comb(n, n - k) end
  nume = Int64(1)
  deno = Int64(1)
  for i = 0:k - 1
    nume *= n - i
    deno *= i + 1
    nume %= MOD
    deno %= MOD
  end
  return nume * modpow(deno, MOD - 2) % MOD
end

function modpow(a::Integer, p::Integer)
  if p == 0
    return 1
  elseif p % 2 == 0
    return modpow(a, Int64(p / 2))^2 % MOD
  else
    return a * modpow(a, p - 1) % MOD
  end
end

main()


Measured memory_bytes: 114560
N = int(input())
D, X = [int(n) for n in input().split()]
A = [int(input()) for _ in range(N)]

s = 0

for a in A:
    if a == 1:
        s += D // a
    else:
        s += sum([1 for d in list(range(1, D+1)) if d % a == 1])

print(s + X)

Measured memory_bytes: 3060
using System;
using System.Linq;

namespace Sample101
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            int[] cardsS = new int[13];
            int[] cardsH = new int[13];
            int[] cardsC = new int[13];
            int[] cardsD = new int[13];
            for (int i = 0; i < n; i++)
            {
                var line = Console.ReadLine().Split(' ');
                var mark = line[0];
                var rank = int.Parse(line[1]);
                switch (mark)
                {
                    case "S":
                        cardsS[rank - 1] = 1;
                        break;
                    case "H":
                        cardsH[rank - 1] = 1;
                        break;
                    case "C":
                        cardsC[rank - 1] = 1;
                        break;
                    case "D":
                        cardsD[rank - 1] = 1;
                        break;
                }
            }

            for (int i = 0; i < cardsS.Length; i++)
            {
                if (cardsS[i] == 0)
                {
                    Console.WriteLine("S " + (i + 1));
                }
            }
            for (int i = 0; i < cardsH.Length; i++)
            {
                if (cardsH[i] == 0)
                {
                    Console.WriteLine("H " + (i + 1));
                }
            }
            for (int i = 0; i < cardsC.Length; i++)
            {
                if (cardsC[i] == 0)
                {
                    Console.WriteLine("C " + (i + 1));
                }
            }
            for (int i = 0; i < cardsD.Length; i++)
            {
                if (cardsD[i] == 0)
                {
                    Console.WriteLine("D " + (i + 1));
                }
            }
        }
    }
}


Measured memory_bytes: 15924
#include<bits/stdc++.h>
    using namespace std;
    #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define ll long long int
    #define fi first
    #define se second
    #define pb push_back
    #define pii pair < int , int >
    #define mp make_pair
    #define vec vector < ll >
    #define vecp vector < pii  >
    #define forl(i,q1,n,q2) for(ll i=q1;i<q2;i++)
    #define null NULL
    #define mm 1000005

    int main()
    {

      // unordered_map< pair<char,int> ,ll> :: iterator itr;
      map<ll,ll>m1,m2;
      map<ll,ll> :: iterator itr;
        ll n;
        cin>>n;
        vecp v;
        forl(i,0,n,n)
        {
            ll a,b;
            cin>>a>>b;
            ll p,q;
            p=b;q=a;
            v.pb(mp(p,q));
        }
        sort(v.begin(),v.end());
        ll sum=0;
        forl(i,0,n,n)
        {
            sum=sum+v[i].se;
            if(sum>v[i].fi)
            {
                cout<<"No"<<endl;
                return 0;

            }
        }
        cout<<"Yes"<<endl;


}


Measured memory_bytes: 2420
#include<stdio.h>
#include<stdlib.h>

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(void){

int n=0;
int i;
int j;
int tmp;
int s=0;
int d[100000];
int flag=0;
  
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&d[i]);
}

qsort(d, n, sizeof(int), compare_int);
  
s=n/2;
  
if(d[s]==d[s-1]){
printf("0\n");
} else {
printf("%d\n",d[s]-d[s-1]); 
}
  
return 0;
  
}

Measured memory_bytes: 892
#include <cstdio>
#include <iostream>

using namespace std;

int main() {

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

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

	int cnt = 0;

	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; ++i) {
		int T;
		scanf("%d", &T);

		int left = 0;
		int right = n;
		int mid = (right + left) / 2;

		while (left < right) {
			if (T > S[mid]) {
				left = mid + 1;
			} else if (T < S[mid]) {
				right = mid;
			} else {
				++cnt;
				break;
			}
			mid = (right + left) / 2;
		}
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 3508
s=input()
n=len(s)
accum=[[0]*(n+1) for _ in range(26)]
for i in range(n):
    accum[ord(s[i])-ord("a")][i+1]+=1
for i in range(n):
    for j in range(26):
        accum[j][i+1]+=accum[j][i]
for i in range(n-1):
    for j in range(26):
        if accum[j][i+2]-accum[j][i]==2:
            print(i+1,i+2)
            exit()
for i in range(n-2):
    for j in range(26):
        if accum[j][i+3]-accum[j][i]==2:
            print(i+1,i+3)
            exit()
print(-1,-1)

Measured memory_bytes: 106192
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

bool map[1000000*3+1];

int main() {

  int s;
  cin >> s;

  int a = s;
  map[a] = true;
  int ans = 0;
  for (int i = 1; i <= 1000000; i++) {
    if (a%2) a = a*3 + 1;
    else     a = a/2;
    if (map[a]) {
      ans = (i+1);
      break;
    }
    else {
      map[a] = true;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;

public class Main {

  private static void solve() {
    int n = ni();
    long[] a = nal(n + 1);
    long total = Arrays.stream(a).sum();

    long ret = 0;
    long now = 1;
    for (int i = 0; i < n; i++) {
      ret += now;
      total -= a[i];
      now = Math.min((now - a[i]) * 2, total);
      if (now < 0) {
        System.out.println(-1);
        return;
      }
    }
    if (now != a[n]) {
      System.out.println(-1);
      return;
    }
    ret += now;
    System.out.println(ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 47928
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PI 3.14159265358979323846264338327950L

#define int long long

template<typename A, size_t N, typename T>

void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//ここにグローバル変数宣言

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//ここに関数宣言




//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int N,M;
cin>>N>>M;
int H[N];
REP(i,N){cin>>H[i];}
vector<vector<int> > G(N);

REP(i,M){
	int A,B;
	cin>>A>>B;
	A--;B--;
	G[A].PB(B);
	G[B].PB(A);
}
//
int cnt=0;

REP(i,N){
	bool good=true;
	if (G[i].empty()){cnt++; continue;}
	for (auto h : G[i])
	{
		if (H[h]>=H[i]){good=false; break;}
	}
	if (good){cnt++;}

}
cout<<cnt<<endl;







return 0;

}


Measured memory_bytes: 9728
N, A, B = map(int, input().split())
cy = N // (A + B)
cynum = N % (A + B)
tmpans = cy * A

#print(cy)
#print(cynum)
#print(tmpans)

if 0 <= cynum and cynum < A:
    ans = cynum + tmpans
else:
    ans = tmpans + A
print(ans)

Measured memory_bytes: 2940
//BISMILLAHHIR RAHMANIR RAHIM
#include<bits/stdc++.h>
using namespace std;
typedef long long int            ll;
typedef unsigned long long int   ull;
#define min3(a,b,c)              min(a,min(b,c))
#define F                        first
#define S                        second
#define PB                       push_back
#define MP                       make_pair
#define PI                       2*acos(0.0)
#define MOD                      998244353
int main()
{
   int n,x,y;
   cin>>n;
   x=n%1000;
   if(x==0)cout<<0<<endl;
   else cout<<(1000-x)<<endl;
}


Measured memory_bytes: 3644
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

/**
 * Shopping
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		line = br.readLine();

		int N, m;
		N = parseInt(line.substring(0, line.indexOf(' ')));
		m = parseInt(line.substring(line.indexOf(' ') + 1));

		if (m == 0) {
			System.out.println(N + 1);
			return;
		}

		int[] shops = new int[N + 1];

		for (int i = 0; i < m; i++) {
			line = br.readLine();
			int c, d;
			c = parseInt(line.substring(0, line.indexOf(' ')));
			d = parseInt(line.substring(line.indexOf(' ') + 1));
			shops[c]++;
			shops[d]--;
		}

		for (int i = 1; i < shops.length; i++) {
			shops[i] += shops[i - 1];
		}

		int free = 0;
		for (int i = 0; i < shops.length; i++) {
			if (shops[i] == 0) free++;
		}

		System.out.println(free + (N + 1 - free) * 3);

	}
}

Measured memory_bytes: 25072
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var nk = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			int n = nk[0];
			int k = nk[1];
			var h = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

			var dp = new long[n];
			for (int i = 0; i < n; i++) {
				dp[i] = long.MaxValue;
			}

			dp[0] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 1; j <= k; j++) {
					if (i + j < n) {
						dp[i + j] = Math.Min(
							dp[i + j],
							dp[i] + Math.Abs(h[i] - h[i + j]));
					}
				}
			}

			Console.WriteLine(dp[n - 1]);
		}
	}
}

Measured memory_bytes: 21728
use std::io;
use std::str;

pub struct Scanner<R> {
    reader: R,
    buffer: Vec<String>,
}

impl<R: io::BufRead> Scanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buffer: vec![],
        }
    }

    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            self.reader.read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }

    pub fn tokens<T: str::FromStr>(&mut self) -> Vec<T> {
        assert!(self.buffer.is_empty());
        let mut input = String::new();
        self.reader.read_line(&mut input).expect("Failed read");
        input
            .split_whitespace()
            .map(|x| x.parse().ok().expect("Failed parse"))
            .collect()
    }
}

// f(0, W) = 0
// f(n, W) = f(n - 1, W)
// f(n, W) = f(n - 1, W - weights[n]) + values[n]
fn solve<R: io::BufRead, W: io::Write>(scan: &mut Scanner<R>, out: &mut W) {
    let n: usize = scan.token();
    let max_weight: usize = scan.token();
    let mut weights = Vec::new();
    let mut values = Vec::new();
    for i in 0..n {
        weights.push(scan.token::<i64>());
        values.push(scan.token::<i64>());
    }
    let mut dp = vec![0; max_weight + 1];
    for i in 0..n {
        let mut new_dp = vec![0; max_weight + 1];
        for w in 0..=max_weight {
            new_dp[w] = dp[w];
            if (w as i64) - weights[i] >= 0 {
                new_dp[w] = new_dp[w].max(dp[w - weights[i] as usize] + values[i]);
            }
        }
        dp = new_dp;
    }
    let ans = dp[max_weight];
    writeln!(out, "{}", ans).ok();
}

fn main() {
    let (stdin, stdout) = (io::stdin(), io::stdout());
    let mut scan = Scanner::new(stdin.lock());
    let mut out = io::BufWriter::new(stdout.lock());
    solve(&mut scan, &mut out);
}


Measured memory_bytes: 3404
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main(){
	int n;
	double up, down, tmp;
	cin >> n;
	vector<double> a(n);
	for(int i=0; i<n; i++){
		cin >> a[i];
	}

	for(int i=0; i<n; i++){
		down += 1/a[i];
	}
	down = 1/down;

	cout << fixed << setprecision(7);
	cout << down << endl;
	return 0;
}



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

    int n;
    cin >> n;
    vector<int> p(n);
    rep(i, n) cin >> p[i];

    int m = p[0];
    int ans = 0;
    rep(i, n){
        if(m >= p[i]){
            ans++;
            m = p[i];
        }
    }
    cout << ans << endl;

    return 0;
}

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

int f_xor(char a, char b){
    if(a == '0' && b == '0'){
        return 0;
    }
    else if(a == '0' && b == '1'){
        return 1;
    }
    if(a == '1' && b == '0'){
        return 1;
    }
    else{
        return 0;
    }
}

int main(){
    string S; cin >> S;
    size_t len = S.length();
    string a,b;
    for(int i=0; i<len; i++){
        if(i%2){
            a += '0';
            b += '1';
        }
        else{
            a += '1';
            b += '0';
        }
    }

    int res_a = 0;
    int res_b = 0;
    for(int i=0; i<len; i++){
        res_a += f_xor(a[i],S[i]);
        res_b += f_xor(b[i],S[i]);
    }
    cout << ((res_a < res_b) ? res_a : res_b) << endl;
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main(){
	char a[10];
	cin >> a[0] >> a[1] >> a[2];
	int five=0;
	int seven=0;
	for(int i=0;i<3;i++){
		if(a[i]=='5'){
			five++;
		}else if(a[i]=='7'){
			seven++;
		}
	}
	if(five==2 && seven==1){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){

int r=100000;
int n,a;

scanf("%d",&n);


for(int i = 0; i<n; i++){
 r = r*1.05;

if(r%1000 > 0){
a=r%1000;
r=r+1000-a;
}
}
printf("%d\n",r);

return 0;
}


Measured memory_bytes: 2048
import java.util.Scanner;
 class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int yoko = sc.nextInt(), tate = sc.nextInt();
		int x = sc.nextInt(), y = sc.nextInt(),r = sc.nextInt();
		if(x+r <= yoko && x-r >= 0){
			if(y+r <= tate && y-r >= 0){
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		} else {
			System.out.println("No");
		}
	}
 }
 

Measured memory_bytes: 26348
#include <stdio.h>

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


Measured memory_bytes: 512
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
c = Counter(a)

ans = 0
for x in a:
    if c[x] == 0:
        continue
    temp = (1 << x.bit_length()) - x
    c[x] -= 1
    if temp in c.keys():
        if c[temp] > 0:
            c[temp] -= 1
            ans += 1

print(ans)



Measured memory_bytes: 33296
# D - Floor Function

from math import floor

A, B, N = map(int, input().split())

if B <= N:
    mx = floor(A * (B - 1) / B) - A * floor((B - 1) / B)
else:
    mx = floor(A * N / B) - A * floor(N / B)

# mx = -1 * float('inf')
# i = 0

# for i in range(N + 1):
#     result = floor(A * i / B) - A * floor(i / B)
#     print(i, result)
#     if mx <= result:
#         mx = result

print(mx)


Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define ld long double
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef vector <ll> vi;
#define out(x) return cout<<x,0;
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define lc(n) 2*n+1
#define rc(n) 2*n+2
#define fill(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL)); 
const ll N = 55, M = 35;

int main(){
    FAST;
    ll n, x = 0, m, k, i, t, ans = 0, j, y = 0, z = 0, c = 0;
    cin >> n;
    ll a[n];
    map < ll , ll > mp;
    for ( i = 0 ; i < n ; i ++ ) {
        cin >> a[i];    
        mp[a[i]] ++;
    }
    for ( auto it : mp ){
        x = it.ss;
        if ( x > 1 ){
            ans += (x*(x - 1))/2;
        }
    }
    for ( i = 0 ; i < n ; i ++ ){
        x = mp[a[i]];
        if ( x > 1 )
            ans -= (x*(x - 1)) / 2;
        x --;
        if ( x > 1 )
            ans += (x*(x - 1))/2;
        cout << ans << "\n";
        if ( x > 1 )
            ans -= (x*(x - 1))/2;
        x ++;
        if ( x > 1 )
            ans += (x*(x - 1)) / 2;
    }
}

Measured memory_bytes: 11136