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

#define IOS                               \
	ios_base::sync_with_stdio(false); \
	cin.tie(0);                       \
	cout.tie(0);                      \
	cin.exceptions(cin.failbit);
#define int long long int //Comment when Unnecessary
#define ll long long
#define sz(a) (int)((a).size())
#define all(a) a.begin(), a.end()
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define pii pair<int, int>
#define vi vector<int>
#define F first
#define S second
#define endl "\n" // Remove on Interactive

const int N = 300009;
const int mod = 1000000007;

int exp(int a, int b)
{
	if (b == 0)
		return 1;
	int x = exp(a, (b / 2));
	x *= x;
	x %= mod;
	if (b % 2)
		x *= a;
	x %= mod;
	return x;
}

int inverse(int a)
{
	return exp(a, mod - 2);
}

int fac1(int z)
{
	int er = 1;
	rep(i, 1, z + 1)
	{
		er *= i;
		er %= mod;
	}
	return er;
}

int fac(int n, int a)
{
	int er = 1;
	rep(i, (n - a + 1), n + 1)
	{
		er *= i;
		er %= mod;
	}
	er *= inverse(fac1(a));
	er %= mod;
	return er;
}

int fact[N];

void pre()
{
	fact[0] = 1;
	rep(i, 1, N)
	{
		fact[i] = fact[i - 1] * i;
		fact[i] %= mod;
	}
}

int32_t main()
{
	IOS;
	pre();
	int n, k;
	cin >> n >> k;
	int num = min(n - 1, k);
	int ans = 0;
	int now = 1;
	for (int i = 1; i <= (num + 1); i++)
	{
		int now1;
		now1 = now * fact[n];
		now1 %= mod;
		now1 *= inverse(fact[i - 1]);
		now1 %= mod;
		now1 *= inverse(fact[n - i + 1]);
		now1 %= mod;
		ans += now1;
		ans %= mod;
		now *= (n - i);
		now %= mod;
		now *= inverse(i);
		now %= mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
//#include <windows.h>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VVC = vector<VC>;
using VS = vector<string>;
using VVS = vector<VS>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
const int INF = 2e9;
const LL MOD = 1e9 + 7;

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

void END(){cout << 1 << endl; exit(0);}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  VI a(n);
  int sum = 0;
  REP(i, n)
  {
    cin >> a[i];
    sum += a[i];
  }
  double sd = (double)sum/(double)(4*m);
  int ct = 0;
  REP(i, n) if (a[i] >= sd) ct++;
  if (ct >= m) cout << "Yes";
  else cout << "No";

  return 0;
}

Measured memory_bytes: 256
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#define ll long long
using namespace std;



int main(){
  string S;
  cin>>S;
  if(S[0]==S[1]||S[1]==S[2]||S[2]==S[3]) cout<<"Bad"<<endl;
  else cout<<"Good"<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int A, B, C;
	cin >> A >> B >> C;

	if (A > C && C > B) {
		cout << "Yes" << endl;
	}
	else if (B > C && C > A) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
#define int long long
#define MOD 1e9+7
typedef pair<int,int> P;
typedef pair<int,P> PP;

signed main(){
  while(1){
  int n,w,d;
  cin>>n>>w>>d;
  if(n+w+d==0)break;
  vector<P> v;
  v.pb(P(w,d));
  for(int i=0;i<n;i++){
    int p,s;
    cin>>p>>s;
    p--;
    P t=v[p];
    v.erase(v.begin()+p);
    int tw=t.fi;
    int td=t.se;
    s%=tw+td;
    if(s>tw){
	 s-=tw;
	 v.pb(P(tw,min(td-s,s)));
	 v.pb(P(tw,max(td-s,s)));
    }else{
	 v.pb(P(min(tw-s,s),td));
	 v.pb(P(max(tw-s,s),td));
    }
  }
  vector<int> ans;
  for(int i=0;i<v.size();i++)ans.pb(v[i].fi*v[i].se);
  sort(all(ans));
  for(int i=0;i<ans.size();i++){
    if(i)cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 3088
n = int(input())
a = [int(i) for i in input().split()]
x = (sum(a)-sum(a)%n)//n
answer,answer2 = 0,0
for i in a:
	answer += (i-x)**2
for i in a:
	answer2 += (i-(x+1))**2
print(min(answer,answer2))

Measured memory_bytes: 3060
def lcs c1, c2, l, m
	dp = Array.new(m + 1){0}
	l.times do |i|
		tmp = dp.dup
		m.times do |j|
			jj = j + 1
			if c1[i] == c2[j]
				dp[jj] = tmp[jj - 1] + 1
			elsif  dp[jj] < dp[jj - 1] 
				dp[jj] = dp[jj - 1]
			end
		end
	end
	return dp[-1]
end

n = gets.to_i
n.times do
	c1 = gets.chomp.split("")
	c2 = gets.chomp.split("")
	l = c1.size
	m = c2.size
	puts lcs(c1, c2, l, m)
end

Measured memory_bytes: 52864
h,w = map(int,input().split())
stage = [["#" for x in range(w+2)] for x in range(h+2)]
for i in range(1,h+1):
    stage[i][1:w+1] = list(input())
dp = [[0 for x in range(w+2)] for x in range(h+2)]
dp[1][1] = 1
for j in range(1,h+1):
    for i in range(1,w+1):
        dp[j][i] = dp[j][i]%(10**9+7)
        if(stage[j+1][i] == "."):
            dp[j+1][i] += dp[j][i]
        if(stage[j][i+1] == "."):
            dp[j][i+1] += dp[j][i]
print(dp[h][w])


Measured memory_bytes: 52312
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    int N;
    cin >> N;
    vec<int> a(N);
    int mx = 0;
    int mn = 0;
    rep(i, N) {
        cin >> a[i];
        mx = max(mx, a[i]);
        mn = min(mn, a[i]);
    }

    cout << N*2-1 << endl;
    if(mx >= abs(mn)){
        int idx = find(all(a),mx) - a.begin() + 1;
        rep(i,N) cout << idx << " " << i+1 << endl;
        rep(i,N-1) cout << i+1 << " " << i+2 << endl;
    } else {
        int idx = find(all(a),mn) - a.begin() + 1;
        rep(i,N) cout << idx << " " << i+1 << endl;
        for(int i=N;i>=2;--i) cout << i << " " << i-1 << endl;
    }
}

Measured memory_bytes: 256
from collections import Counter
N = int(input())
S = list(input())
ans = 10 ** 9
hash = [0] * (N + 1)
memo = 0
for i in range(N):
  if S[i] == "#":
    memo += 1
  hash[i + 1] = memo
dot = [0] * (N + 1)
memo = 0
for i in range(N - 1,-1,-1):
  if S[i] == ".":
    memo += 1
  dot[i] = memo    
for i in range(N + 1):
  ans = min(ans, hash[i] + dot[i])
print(ans)  

Measured memory_bytes: 85680
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*n
for i in range(n-1):
    lst[a[i]-1]+=1
print(*lst)

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

using namespace std;

const int NS = (int)2e3 + 5, mod = 998244353;
int dp[NS << 1][NS << 1];
vector<int> redBall, blueBall;
string s;

int add(int _a, int _b) {
    _a += _b;
    if (_a >= mod) _a -= mod;
    return _a;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> s;
    for (int i = 0; i < (int)s.size(); ++i) {
        if (s[i] == '0') redBall.push_back(i + 1), redBall.push_back(i + 1);
        else if (s[i] == '1') redBall.push_back(i + 1), blueBall.push_back(i + 1);
        else blueBall.push_back(i + 1), blueBall.push_back(i + 1);
    }

    dp[0][0] = 1;
    for (int rPlusB = 0; rPlusB < 2 * (int)s.size(); ++rPlusB) {
        for (int r = 0; r <= min(rPlusB, (int)redBall.size() ); ++r) {
            int b = rPlusB - r;
            if (!dp[r][b]) continue ;
            if (r != (int)redBall.size() && redBall[r] <= r + b + 1) {
                dp[r + 1][b] = add(dp[r + 1][b], dp[r][b]);
            }
            if (b != (int)blueBall.size() && blueBall[b] <= r + b + 1) {
                dp[r][b + 1] = add(dp[r][b + 1], dp[r][b]);
            }
        }
    }

    cout << dp[redBall.size()][blueBall.size()];

    return 0;
}


Measured memory_bytes: 60544
#include<bits/stdc++.h>
using namespace std;
int main(){
  string a;
  cin >> a;
  int count  = 0;
  vector<int> key(26);
  for(int i=0;i<a.size();i++){
    key.at(a.at(i)-97)++;
  }
  for(int i = 0;i< 26;i++){
    if(key.at(i) == 0){
      cout << (char)(i+97) << endl;
      count = 1;
      break;
    }
  }
  if(count == 0)
    cout << "None" << endl;
}   


Measured memory_bytes: 512
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n, a, b = MAP()
if (a - b) % 2 == 0:
    print(abs(a - b) // 2)
    exit()
print(abs(a - b) // 2 + min(min(a, b) - 1, n - max(a, b)) + 1)

Measured memory_bytes: 59628
#include<stdio.h>
int main()
{
long long int a,b,c;
  scanf("%lld",&a);
  b=0;
  c=100;
  while(c<a)
  {
  c=c*1.01;
  b++;
  }
  
  
 printf("%lld",b);
  
return 0;
}

Measured memory_bytes: 1732
#include<stdio.h>
int selectionSort(int A[],int N){
int i,j,t,minj,sw=0;
for(i=0;i<N-1;i++){
minj=i;
for(j=i;j<N;j++){
if(A[j]<A[minj]) minj=j;
}
t=A[i];A[i]=A[minj];A[minj]=t;
if(i!=minj)sw++;
}
return sw;
}
int main(){
int i,A[100], N,sw;
scanf("%d",&N);
for(i=0;i<N;i++)scanf("%d",&A[i]);

sw=selectionSort(A,N);
for(i=0;i<N;i++){
if(i>0)printf(" ");
printf("%d", A[i]);
}
printf("\n");
printf("%d\n",sw);
return 0;
}

Measured memory_bytes: 604
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

amari = 0
cnt = 0
for i in range(n):
    if a[i] >= b[i] + amari:
        cnt += b[i] + amari
    else:
        cnt += a[i]
        
    if amari > a[i]:
        amari = b[i]
    elif amari + b[i] > a[i]:
        amari = amari+b[i] - a[i]
    else:
        amari = 0

cnt += a[n] if amari >= a[n] else amari

print(cnt)



Measured memory_bytes: 18624
import math
import random

cands=[2*x+3 for x in range( int(10**4.5)+1 )]
primes=[2]
while(1):
    y=cands.pop(0)
    primes.append(y)
    cands=[x for x in cands if x%y!=0]
    if y>cands[-1]**0.5:
        break
primes=primes+cands

S=int(input())

X=math.ceil(S**0.5)
Y=X
sol=0
if X**2==S:
    print(0,0,X,0,0,X)
else:    
    while(sol==0):
        ab=X*Y-S
        cc=[1,1,0]
        t=0
        XX=ab
        XY=[X,Y,10**19]
        for p in primes:
            while( XX%p==0):
                XX//=p
                cc[t]*=p
                if cc[t]>XY[0]:
                    t+=1
                    cc[t-1]//=p
                    cc[t]*=p
            if cc[0]>X or cc[1]>Y:
                sol=2
                break
            elif XX==1:
                sol=1
                break
        if cc[0]>cc[1]:
            cc[1]*=XX
        else:
            cc[0]*=XX
        if cc[0]<X and cc[1]<Y:
            sol=1
        if sol==1:
            print(0,0,Y,cc[0],cc[1],X)
        elif sol != 1:
            X+=1
            Y+=1
            sol=0

Measured memory_bytes: 42604
#include <bits/stdc++.h>
using namespace std;
 
int judge(int x) {
  int a, b, c, d;
  a = x / 10000;
  b = x / 1000 % 10;
  c = x / 10 % 10;
  d = x % 10;
  if (a == d && b == c) {
    return 1;
  }
  else {
    return 0;
  }
} 

int main() {
  int A, B, sum = 0;
  cin >> A >> B;
  for (int i=A; i <= B; i++) {
    sum += judge(i);
  }
  cout << sum << endl;
}


Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 200000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<31-1;
const int MOD = 1000000007;

void solve(void){
    string S;
    cin >> S;
    int L = S.length();
    int ans = L, id = 0;
    while (id < L) {
        while(S[id] == 'T' && id < L) id++;
        if (id >= L-1) break;
        int cnts = 1, cntt = 0;
        while(cnts > cntt && id < L-1) {
            id++;
            if (S[id] == 'S') cnts++;
            else cntt++;
        }
        if (cnts==cntt) ans -= cnts*2;
        else ans -= cntt*2;
    }
    cout << ans << endl;
}

int main(void){
  solve();
  //cout << "yui(*-v・)yui" << endl;
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int N;
  long long K;
  vector<pair<int, int> > array;

  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    array.push_back(make_pair(a, b));
  }

  sort(array.begin(), array.end());

  int i = 0;
  long long cnt = 0;
  int ans;
  while (cnt < K) {
    if (cnt + array[i].second >= K) {
      ans = array[i].first;
      break;
    }
    cnt += array[i].second;
    i++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1400
N = gets.strip.to_i
cards = gets.strip.split(" ").map(&:to_i)
MAX = N - 1
(0..MAX).each do |i|
  (i..MAX).each do |j|
    cards[i], cards[j] = cards[j], cards[i] if cards[i] < cards[j]
  end
end
result = 0
cards.each_with_index do |num, i|
  i.even? ? result += num : result-= num
end
puts result

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

using i64 = long long int;

int n, k;
vector<int> v;

bool check(int p){
    int cnt = 0, idx = 0;
    for(int i=0;i<k;++i){
        int acc = 0;
        while (idx < n && acc + v[idx] <= p) {
            acc += v[idx];
            idx++;
        }
        if(idx >= n)return true;
    }
    return false;
}

int bsearch(int ng, int ok){
    while(abs(ok-ng) > 1){
        int mid = (ok+ng) / 2;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    return ok;
}

int main(){
    cin >> n >> k;
    for(int i=0;i<n;++i){
        int w;
        cin >> w;
        v.push_back(w);
    }

    cout << bsearch(0, 1e9) << endl;

    return 0;
}



Measured memory_bytes: 3528
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	int n;
	cin >> n;
	int t = 0;
	int x = 0;
	int y = 0;
	for (int i = 0; i < n; ++i) {
		int nt, nx, ny;
		cin >> nt >> nx >> ny;
		int df = abs(x - nx) + abs(y - ny);
		int df2 = abs(nt - t);
		if (df % 2 == df2 % 2 && df2 >= df) {
			t = nt, x = nx, y = ny;
		}
		else {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;
}




Measured memory_bytes: 256
a = input("")
b = list(a)
j = 0;
k = 0;
for m in b:
    if int(m) == 0 or int(m) == 1:
        k = k+1;
if k == len(b):
    if (int(b[0])==1 or int(b[0])==0) and len(b) == 1:
        j = 0
    else:
        for i in range(len(b)-1):
            if(b[i]==b[i+1]):
                if int(b[i]) == 0:
                    b[i+1] = "1"
                else:
                    b[i+1] = "0"
                j = j + 1;
            
print(j)
                

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

#include <cstdio>
#include <map>
using namespace std;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)

typedef long long ll;

int main() {
    map<string, int> cnt;
    int N;
    cin >> N;
    rep(i, N) {
        string S;
        cin >> S;
        cnt[S]++;
    }
    printf("AC x %d\n", cnt["AC"]);
    printf("WA x %d\n", cnt["WA"]);
    printf("TLE x %d\n", cnt["TLE"]);
    printf("RE x %d\n", cnt["RE"]);
    return 0;
}


Measured memory_bytes: 3728
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long 
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back 
#define mp make_pair
#define inf 2000000009
#define mod 1000000007
using namespace std;

int main()
{ 
   ll n,w;
   cin>>n>>w;

   ll wt[n],val[n];
   for(ll i=0;i<n;i++)
   	cin>>wt[i]>>val[i];

   ll dp[n+1][w+1];

   for(ll i=0;i<n+1;i++)
   {
   	for(ll j=0;j<w+1;j++)
   	{
   		if(i==0 or j==0)
   			dp[i][j]=0;
   		else
   		{
   			dp[i][j]=dp[i-1][j];

   			if(wt[i-1]<=j)
   				dp[i][j]=max(dp[i][j],dp[i-1][j-wt[i-1]]+ val[i-1]);
   		}
   	}
   }
   cout<<dp[n][w]<<endl;
}


Measured memory_bytes: 79104
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
int main(void){
    ll n;
    cin >> n;
    vector<vector<ll>> g(n+1);
    map<p, ll> I{};
    for(ll i = 0; i < n-1; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        I[p(a, b)] = c;
        g[a].push_back(b);
        g[b].push_back(a);
        I[p(a,b)] = I[p(b,a)] = c;
    }
    ll q, k;
    cin >> q >> k;
    vector<p> c;
    for(ll i = 0; i < q; i++){
        ll a, b;
        cin >> a >> b;
        c.push_back(p(a,b));
    }
    vector<ll> use(n+1, -1);
    vector<ll> ans(n+1, 0);
    use[k] = 0;
    ans[k] = 0;
    queue<ll> que;
    que.push(k);
    ll MAX = 0;
    while(!que.empty()){
        ll v = que.front();
        que.pop();
        for(ll nv : g[v]){
            if(use[nv]!=-1) continue;
            ans[nv] = ans[v]+I[p(v,nv)];
            que.push(nv);
            use[nv] = 1;
        }
    }
    for(ll i = 0; i < q; i++){
        ll a = c[i].first, b = c[i].second;
        cout << ans[a]+ans[b] << endl;
    }
return -0;
}


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

long long int n, m;
vector< vector< long long int > > v;
long long int ans;

void kansu( long long int k, bool f[10], long long int cnt ) {

  if ( cnt == n ) {
    ans++;
    return;
  }

  for ( long long int i = 0; i < v[k].size(); i++ ) {

    long long int p = v[k][i];
    if ( f[p] == false ) {
      f[p] = true;
      kansu( p, f, cnt + 1 );
      f[p] = false;
    }

  }

  return;
}

int main() {

  cin >> n >> m;

  for ( long long int i = 0; i < n; i++ ) {
    vector < long long int > vv;
    v.push_back( vv );
  }

  for ( long long int i = 0; i < m; i++ ) {

    long long int a, b;
    cin >> a >> b;
    a--;
    b--;
    v[a].push_back( b );
    v[b].push_back( a );

  }

  ans = 0;
  bool f[10] = {};
  f[0] = true;
  kansu( 0, f, 1 );

  cout << ans << endl;

  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define REP(i,n) for(int i=0;i<n;++i)
#define INF (2<<30)
using namespace std;

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  cout << (b % a == 0 ? (a + b) : (b - a)) << endl;

  return 0;
}


Measured memory_bytes: 256
g[10][10],m,a,b,c,s,A,S,*p;main(n){for(;~scanf("%d",&m);n&&printf("%d %d\n",A,S)){memset(g,1,400);for(n=-1;m--;g[a][b]=g[b][a]=c)scanf("%d%d%d",&a,&b,&c),a>n?n=a:0,b>n?n=b:0;for(m=++n;m--;)for(S=1e9,a=n;a--;s>S||(S=s,A=a))for(s=0,b=n,p=g[a];b--;a-b?s+=p[b]=p[b]<c?p[b]:c:0)c=p[m]+g[m][b];}}

Measured memory_bytes: 0
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

N = int(input())
graph = [[] for _ in range(N)]

for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))

ans = [0] * N


def dfs(cur, prev, dist):
    if dist % 2 == 0:
        ans[cur] = 1
    else:
        ans[cur] = 0
    for n, d in graph[cur]:
        if n != prev:
            dfs(n, cur, dist + d)


dfs(0, -1, 0)
for a in ans:
    print(a)


Measured memory_bytes: 156060
#include<stdio.h>
#include<iostream>
using namespace std;

int N;
int tb[110];
int rec(int x){
    if( x > 100) return 0;
    tb[x] = 1;
    rec(x+4);
    rec(x+7);
}

int main (){
    cin >> N;
    rec(0);
    cout << ( tb[N] ? "Yes" : "No" ) << endl;
    return 0;
}


Measured memory_bytes: 256
/*  ex7_3
    Rikuta  */

#include <stdio.h>

int main(void)
{
    int height, width, flag;
    char **matrix_given;
    int **on_off_matrix;

    //与えられる行列の高さと幅の入力
    scanf("%d %d\n", &height, &width);

    matrix_given = (char **)calloc(height, sizeof(char *));
    if (matrix_given==NULL)
    {
        exit(1);
    }
    for (int i = 0; i < height; i++)
    {
        matrix_given[i] = (char *)calloc(width+1, sizeof(char));
        if (matrix_given[i]==NULL)
        {
            exit(1);
        }
        
    }

    on_off_matrix = (int **)calloc(height, sizeof(int *));
    if (on_off_matrix == NULL)
    {
        exit(1);
    }
    for (int i = 0; i < height; i++)
    {
        on_off_matrix[i] = (int *)calloc(width+1, sizeof(int));
        if (on_off_matrix[i] == NULL)
        {
            exit(1);
        }
    }
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width + 1; j++)
        {
            //改行込みで与えられた行列を受け取る
            scanf("%c", &matrix_given[i][j]);
        }
    }
    for (int i = 0; i < height; i++)
    {
        //フラグを立てる
        flag = 1;
        for (int j = 0; j < width; j++)
        {
            if (matrix_given[i][j] == '#')
            {
                //i行について着目したときに#が一個でもあればフラグを0とする
                flag = 0;
            }
        }
        //もしi行について#がいっこもなければ
        if (flag)
        {
            for (int j = 0; j < width + 1; j++)
            {
                //on_off_matrixのi行目を1にする
                on_off_matrix[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < width; i++)
    {
        //フラグを立てる
        flag = 1;
        for (int j = 0; j < height; j++)
        {
            if (matrix_given[j][i] == '#')
            {
                //i列について着目したときに#が一個でもあればフラグを0にする
                flag = 0;
            }
        }
        //i列について，#がなければ
        if (flag)
        {
            for (int j = 0; j < height; j++)
            {
                //on_off_matrixのi列目を1にする
                on_off_matrix[j][i] = 1;
            }
        }
    }

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width + 1; j++)
        {
            if (!on_off_matrix[i][j])
            {
                //与えられた行列の要素に対応するon_off_matrixが0ならばそれを出力する．
                printf("%c", matrix_given[i][j]);
            }
        }
    }

    for (int i = 0; i < height; i++)
    {
        free(matrix_given[i]);
        free(on_off_matrix[i]);
    }
    free(matrix_given);
    free(on_off_matrix);

    return 0;
}

Measured memory_bytes: 1676
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007;
ll dp[3005][3005];

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

  rep(i,N){
    dp[0][i] = 1;
  }

  rep(i,N-1){
    vector<ll> tmp(3005, 0);
    rep(j,N-i){
      if(S[i] == '<'){
        tmp[j] += dp[i][j];
        tmp[j] %= MOD;
        tmp[N-i] += MOD - dp[i][j];
        tmp[N-i] %= MOD;
      }else{
        tmp[0] += dp[i][j];
        tmp[0] %= MOD;
        tmp[j] += MOD - dp[i][j];
        tmp[j] %= MOD;
      }
    }
    ll base = 0;
    rep(j,N-i-1){
      base += tmp[j];
      base %= MOD;
      dp[i+1][j] = base;
    }
  }

  cout << dp[N-1][0] << endl;
  
  return 0;
}


Measured memory_bytes: 70016
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>

using namespace std;

int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
	return ans*f;
}

const int N=2e5+5;
int n,l,r,ans;
char s[N];

int main()
{
	n=read();
	scanf("%s",s+1);
	l=1,r=n;
	while(s[l]=='R') l++;
	while(s[r]=='W') r--;
	while(l<=r)
	{
		swap(s[l],s[r]);
		ans++;
		while(s[l]=='R') l++;
		while(s[r]=='W') r--;
	}
	printf("%d\n",ans);
	return 0;
} 

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

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int N, M;
int edges[15][15];
int gain[1<<15];

int dp[15][1<<15];
bool visited[15][1<<15];
const int INF = 1e9;

int rec(int start, int bits){
    if(bits == 0){
        return start == N-1 ? 0 : -INF;
    }
    if(visited[start][bits]) return dp[start][bits];

    int mx = -INF;
    for(int i=0; i<N; i++){
        if(nth_bit(bits, i) && edges[start][i]){
            mx = max(mx, rec(i, bits - (1<<i)) + edges[start][i]);
        }
    }

    for(int bits2=bits; bits2>0; bits2=(bits2-1)&bits){
        mx = max(mx, rec(start, bits - bits2) + gain[bits2 + (1<<start)]);
    }
    dp[start][bits] = mx;
    visited[start][bits] = true;
    return mx;
}

int main(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edges[a][b] = c;
        edges[b][a] = c;
        for(int bits=0; bits<(1<<N); bits++){
            if(nth_bit(bits, a) && nth_bit(bits, b)) gain[bits] += c;
        }
    }
    cout << gain[(1<<N)-1] - rec(0, (1<<N)-2) << endl;
    return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)

typedef long long ll;

int main() {
    int x;
    cin >> x;
    if (x) {
        cout << "0" << endl;
    } else {
        cout << "1" << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
use proconio::input;

const A: usize = 1000_000;

fn main() {
    input! { n: usize }
    let mut a = vec![0; n];
    let mut ac = vec![0; A + 1];
    for i in 0..n {
        input! { ai: usize }
        a[i] = ai;
        ac[ai] += 1;
    }

    let mut pc = true;
    for i in 2..=A {
        let mut c = 0;
        for j in (0..=A).skip(i).step_by(i) {
            c += ac[j];
        }
        if c > 1 {
            pc = false;
            break;
        }
    }

    println!("{} coprime", if pc {
        "pairwise"
    } else {
        let mut v = a[0];
        for i in 1..n {
            v = num_integer::gcd(v, a[i]);
        }
        if v == 1 {
            "setwise"
        } else {
            "not"
        }
    });
}


Measured memory_bytes: 20536
#include <iostream>
#include <vector>
#include <bitset>

#define rep(i, n) for(int i = 0;i < (n);++i)
using ll = long long;
constexpr ll MAX_K {100000+1};


int main(int argc, char** argv) {
  int N, K;
  std::cin >> N >> K;
  std::vector<ll> a(N, 0);
  rep(i, N) std::cin >> a[i];
  std::bitset<MAX_K> win(0uL);
  for (auto i = 1;i <= K;++i) {
    //win[i]
    rep(j,N) {
      if (a[j] <= i && !win[i-a[j]]) {
        win.set(i);
      }
    }
  }
  std::cout << (win[K]?"First\n":"Second\n");
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
void bfs(int x, VV& tree, vector<bool>& visited, V& ans) {
	queue<int> que;
	que.push(x);
	visited[x] = true;
	while (!que.empty()) {
		int X = que.front();
		que.pop();
		visited[X] = true;
		for (auto c : tree[X]) {
			if (!visited[c]) {
				que.push(c);
				visited[c] = true;
				if (ans[c] == -1) ans[c] = X + 1;
			}
		}
	}
}
int main() { // 問題文はしっかり読め!!!
	int n, m;
	cin >> n >> m;
	VV G(n);
	set<P<int>> st;
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		int prev = st.size();
		if (b < a) swap(a, b);
		st.insert(make_pair(a, b));
		if (prev != st.size()) {
			G[a].push_back(b);
			G[b].push_back(a);
		}
	}
	vector<bool> visited(n, false);
	V ans(n, -1);
	bfs(0, G, visited, ans);
	cout << "Yes" << endl;
	rep1(i, n - 1) {
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 19688
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100005;

int N,L,Q;
int x[MAXN],nxt[MAXN][25];
int ans[MAXN];
//int dis[MAXN];

int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&x[i]);
	scanf("%d%d",&L,&Q);
	memset(nxt,0x3F,sizeof nxt);
	for(int i=1;i<=N;i++)
	{
		nxt[i][0]=lower_bound(x+1,x+N+1,x[i]+L)-x;
		if(x[nxt[i][0]]>x[i]+L)
			nxt[i][0]--;
	}
	for(int j=1;(1<<j)<N;j++)
		for(int i=1;i<=N;i++)
			if(nxt[i][j-1]!=0x3F3F3F3F&&nxt[nxt[i][j-1]][j-1]!=0x3F3F3F3F)
				nxt[i][j]=nxt[nxt[i][j-1]][j-1];

	for(int i=1,a,b;i<=Q;i++)
	{
		scanf("%d%d",&a,&b);
		if(a>b)
			swap(a,b);
		int ans=0;
		for(int j=20;j>=0;j--)
			if(nxt[a][j]<=b)
			{
				a=nxt[a][j];
				ans+=(1<<j);
			}
		if(a<b)
			ans++;
		printf("%d\n",ans);
	}

	return 0;
}


Measured memory_bytes: 10880
_n, m = gets.split.map(&:to_i)
cities = []
count = 0
m.times do
  p, y = gets.split.map(&:to_i)
  cities << { count: count, pref: p, year: y }
  count += 1
end

cities.sort! { |a, b|
  (a[:pref] <=> b[:pref]).nonzero? ||
  a[:year] <=> b[:year]
}

current_pref = 0
number = 1
cities.map! { |city|
  if city[:pref] != current_pref
    current_pref = city[:pref]
    number = 1
  end
  city[:number] = number
  number += 1
  city
}

cities.sort_by { |city| city[:count] }.each do |city|
  puts sprintf "%06d%06d",city[:pref],city[:number]
end


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

map< pair<int,long long>, int>  dp;
vector< long long > e;

void gen_pattern(int pos,int r,long long v){
    if( pos >= 10 ){
        if( r == 0 ){
            e.push_back( v );
        }
        return;
    }
    for(int i = 0 ; r - pos * i >= 0 ; i++){
        gen_pattern(pos+1,r - pos*i,v+((long long)(i)<<((pos-1)*7)));
    }
}

int dfs(int pos,long long v){
    if( pos >= e.size() ) return 0;
    if( dp.count(make_pair(pos,v)) ) return dp[make_pair(pos,v)];
    long long V = v;
    int ans = 0 , c = 0;
    while(1){
        ans = max( dfs(pos+1,v) + c , ans);
        c++;
        bool f = true;
        for(int i = 0 ; i < 9 ; i++){
            int s = v >> (7*i) & 127;
            int x = e[pos] >> (7*i) & 127;
            if( s < x ){
                f = false;
                break;
            }
        }
        if( !f ) break;
        v -= e[pos];
    }
    v = V;
    return dp[make_pair(pos,V)] = ans;
}



int main(){
    int n;
    gen_pattern(1,10,0);
    while(cin >> n && n){
        vector<char> v(10);
        for(int i = 0 ; i < n ; i++){
            int t;
            cin >> t;
            v[t]++;
        }
        int greedy = 0;
        for(int i = 1 ; i < 5 ; i++){
            int u = min(v[i],v[10-i]);
            greedy += u;
            v[i] -= u;
            v[10-i] -= u;
        }
        greedy += v[5] / 2;
        v[5] %= 2;
        long long enc = 0;
        for(int i = 1 ; i < 10 ; i++){
            enc += (long long)(v[i]) << (7 * (i-1));
        }
        dp.clear();
        cout << dfs(0,enc)+greedy << endl;
    }
}

Measured memory_bytes: 64668
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<"!"<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin>>n;
  vi A(n);
  for(auto &a:A)cin>>a;

  ll le=-INF,ri=INF;
  for(int i=0;i<200;i++){
    ll num=le+ri;
    ll lemi=(num+le)/3;
    ll rimi=(num+ri)/3;
    ll lesum=0;
    ll risum=0;
    for(int j=0;j<n;j++){
      lesum+=abs(A[j]-(lemi+j+1));
      risum+=abs(A[j]-(rimi+j+1));
    }
    if(lesum<risum){
      ri=rimi;
    }else{
      le=lemi;
    }
  }

  ll ans=0;
  le=(le+ri)/2;
 
  for(int i=0;i<n;i++){
    ans+=abs(A[i]-(le+i+1));
  }
  cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 1792
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int a[100001];
	int n,x;
	cin>>n>>x;
	int ans;
	for(int i=1;i<=n;i++) cin>>a[i];
	ans=abs(x-a[1]);
	for(int i=2;i<=n;i++)
	{
		ans=__gcd(abs(x-a[i]),ans);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T>
struct DiameterForEdge{
  using Edge = pair<Int, T>;
  vector<T> dp;
  vector<vector<Edge> > G;
  DiameterForEdge(Int n):dp(n),G(n){}
  void add_edge(Int u,Int v,T c){
    G[u].emplace_back(v,c);
    G[v].emplace_back(u,c);
  }
  void dfs(Int v,Int p,Int &s){
    if(p<0) dp[v]=T(0);
    if(dp[s]<dp[v]) s=v; 
    for(Edge e:G[v]){
      Int u=e.first;
      if(u==p) continue;
      dp[u]=dp[v]+e.second;      
      dfs(u,v,s);
    }
  }
  pair<Int, Int> endPoints(){
    Int s=0;
    dfs(s,-1,s);
    Int t=s;
    dfs(t,-1,t);
    return make_pair(s,t);
  }
  T build(){
    Int t=endPoints().second;
    return dp[t];
  }
  vector<T> distance(Int v){
    dfs(v,-1,v);
    return dp;
  }
  vector<T> farthest(){
    Int t=endPoints().second;
    auto ds=dp;
    auto dt=distance(t);
    for(Int i=0;i<(Int)ds.size();i++)
      if(ds[i]<dt[i]) ds[i]=dt[i];
    return ds;
  }
};


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  DiameterForEdge<Int> G(n);
  for(Int i=1;i<n;i++){
    Int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    G.add_edge(a,b,c);
  }
  auto vs=G.distance(0);
  for(Int i=0;i<n;i++) cout<<(vs[i]&1)<<"\n";
  cout<<flush;
  return 0;
}


Measured memory_bytes: 10240
n,m = map(int,input().split())
#a = [int(input()) for i in range(m)]
a=set()
for i in range(m):
    tmp=int(input())
    a.add(tmp)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
j=0
for i in range(1,n+1):
  if i in a:
    #dp[a[j]] = 0 
    continue
  if i==1:
    dp[1] = dp[0]
    continue
  dp[i] = dp[i-1]+dp[i-2]
  dp[i]%=mod
print(dp[n])

Measured memory_bytes: 51032
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    unordered_map<ll, ll> hash;
    for (int i = 0; i < N; i++) {
        hash[A[i]]++;
    }

    ll sum = 0;
    for (auto p : hash) {
        sum += p.second * (p.second - 1) / 2;
    }

    for (int i = 0; i < N; i++) {
        ll res = sum;
        ll num = hash[A[i]];
        res -= num * (num - 1) / 2;
        num--;
        res += num * (num - 1) / 2;
        cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 9160
#include <iostream>
#include <string>
#include <array>

#define ALPHA 26

#define INPUT_LEN 12
#define INPUT_SIZE 2
#define DATA_SIZE (1 << (INPUT_LEN * INPUT_SIZE))

bool cache[INPUT_LEN][DATA_SIZE];

int encode(const std::string& dna, const std::array<int, ALPHA> dna_map){
	const int length = dna.length();
	
	int code = 0;
	for(int i = length - 1; i >= 0; i--){
		code <<= INPUT_SIZE;
		code |= dna_map[dna[i] - 'A'];
	}
	
	return code;
}

int main(int argc, char* argv[]){
	std::array<int, ALPHA> dna_map;
	dna_map.fill(-1);
	dna_map['A' - 'A'] = 0;
	dna_map['C' - 'A'] = 1;
	dna_map['G' - 'A'] = 2;
	dna_map['T' - 'A'] = 3;

	int n;
	std::cin >> n;

	for(int i = 0; i < n; i++){
		std::string ops, dna;
		std::cin >> ops >> dna;

		const int code = encode(dna, dna_map);
		const int length = dna.length() - 1;

		if(ops == "insert"){ cache[length][code] = true; }
		else{ std::cout << (cache[length][code] ? "yes" : "no") << std::endl; }
	}
	
	return 0;
}

Measured memory_bytes: 11448
N = int(input())

s = "abcdefghijklmnopqrstuvwxyz"
ans = ""
n, m = 0, 0

for i in range(1, 1000):
    m += 26 ** i
    if N <= m:
        n = i
        break

for i in range(n):
    a, b = divmod(N, 26)
    N = a
    if b == 0:
        ans += s[25]
        N -= 1
    else:
        ans += s[b-1]

ans1 = ''.join(list(reversed(ans)))
print(ans1)

Measured memory_bytes: 9208
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <sstream>
#include <set>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define repp(i,k,n) for(int i=k;i<(int)n;i++)
#define rei(n) for(int i=0;i<(int)n;i++)
#define rel(n) for(int l=0;l<(int)n;l++)
#define all(s) s.begin(),s.end()
#define INT_MAX 2147483647
#define debug(x) cout<<#x<<": "<<x<<endl;
#define PI 2*acos(0,0)
#define pb push_back
#define inin(x) int x; cin>>x;
#define ll long long
#define pb push_back

typedef pair<int, int> pii;
typedef pair<int, pii> pipii;

int main()
{
	while (1)
	{
		inin(x); if (x == 0)break;
		x = abs(x - 1000);
		int ans = 0;
		ans += x / 500; x %= 500;
		ans += x / 100; x %= 100;
		ans += x / 50; x %= 50;
		ans += x / 10; x %= 10;
		ans += x / 5; x %= 5;
		ans += x;
		cout << ans << endl;
	}
}

Measured memory_bytes: 1160
n=int(input())
l=list((map(int,input().split())))
l.sort()
ans=0
for i in range(n-2):
    for j in range(1,n-1):
        for k in range(2,n):
            if i<j<k:
                kari=[l[i],l[j],l[k]]
                if kari[0]!=kari[1]!=kari[2] :
                    if kari[0]+kari[1]>kari[2] and kari[1]-kari[0]<kari[2]:
                        ans+=1    
print(ans)

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;


int a,b,c,m,n,l,ans;

int main(void){
	cin >> a >> b >> c;
	for(;;){
		if(a % 2 == 1 || b % 2 == 1 || c % 2 == 1){
			break;
		}else if(a == b && b == c && c == a){
			ans = -1;
			break;	
		}else{
			m = (b + c) / 2; 
			n = (c + a) / 2;
			l = (a + b) / 2;
			a = m;
			b = n;
			c = l;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=998244353;
const int inf=1<<30;

ll rui(ll a,ll n){
  ll ans=1;
  while(n>0){
    if(n&1) ans=ans*a%mod;
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

int main(){
  int n; cin >> n;
  vector<ll> d(n);
  rep(i,n) cin >> d[i];
  if(d[0]!=0){
    cout << 0 << endl;
    return 0;
  }
  map<ll,ll> mp;
  rep(i,n){
    mp[d[i]]++;
  }
  ll ans=1;
  for(auto c:mp){
    if(c.first==0&&c.second!=1){
      cout << 0 << endl;
      return 0;
    }
    if(c.first>0){
      ans*=rui(mp[c.first-1],c.second);
      ans%=mod;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define repp(i, m, n) for(int i = m; i < n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
typedef pair<ll,ll> pal;
int sz[100010];
int P[100010];
int root(int a)
{
    if(P[a]==a)
    {
        return a;
    }
    else
    {
        return (P[a]=root(P[a]));
    }
}
bool is_the_same_set(int a, int b)
{
    return (root(a)==root(b));
}
void unite(int a, int b)
{
    if(sz[root(a)]<sz[root(b)])
    {
        swap(a, b);
    }
    sz[root(a)]+=sz[root(b)];
    P[root(b)]=root(a);
}
int main()
{
    int n, m, x, y, k;
    int dareka[100010]={};
    cin >> n >> m;
    repp(i, 1, m+1)
    {
        P[i]=i;
        sz[i]=1;
    }
    rep(i, n)
    {
    	cin >> k;
    	cin >> x;
    	dareka[x]=1;
    	if(k>=2)
    	{
    		rep(i, k-1)
	    	{
	    		cin >> y;
	    		dareka[y]=1;
	    		unite(x, y);
	    		x=y;
	    	}
    	}
    }
	int nekko=0;
	int ans=0;
	repp(i, 1, m+1)
	{
		if(dareka[i]==1)
		{
			if(nekko==0)
			{
				nekko=root(i);
			}
			else if(root(i)!=nekko)
			{
				ans=1;
			}
		}
	}
	if(ans==0)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
    return 0;
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int k, x;
 
int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
#endif
	
	cin >> k >> x;
	int tmp = k * 500;
	cout << (tmp >= x ? "Yes" : "No" ) << '\n';
		
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#ifdef _debug
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#define dout(i) //
#endif
using ll = long long;
using ull = unsigned long long;
using ul = unsigned;
double b;
int n;
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 0;i < n;++i){
		int v;
		cin >> v;
		b += (double)1 / v;
	}
	printf("%.10f\n", (double)1 / b);
}

Measured memory_bytes: 256