akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

int main () {
  int n, m;
  cin >> n >> m;

  map<int,ll> mp;
  rep(i,n) {
    int a, b;
    cin >> a >> b;
    if (mp.count(a)) mp[a] += b;
    else mp[a] = b;
  }
  ll ans = 0;
  for (auto shop : mp) {
    ll buy = min((ll)m, shop.se);
    ans += buy*shop.fi;
    m -= buy;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6528
n = int(input())
a = 0
b = 0
ab = 0
total = 0
t = []

for i in range(n):
	t.append(input())

for i in t:
	total += i.count("AB")
	if i[-1] == "A" and i[0] == "B":
		ab += 1
	else:
		a += i[-1] == "A"
		b += i[0] == "B"
if ab == 0:
	print(total + min(a,b))
elif a == 0 and b == 0:
	print(total + ab - 1)
elif a > 0 and b > 0:
	print(total + ab + min(a, b))
else:
	print(total + ab)

Measured memory_bytes: 3700
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;
typedef pair<int, int> P;

int d[510][510];
int main()
{
	int N, M, Q;
	cin >> N >> M >> Q;
	for (int i = 0; i < M; i++) {
		int L, R;
		cin >> L >> R;
		L--; R--;
		d[L][R]++;
	}
	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = 0; j < N; j++) {
			sum += d[i][j];
			d[i][j] = sum;
		}
	}
	for (int j = 0; j < N; j++) {
		int sum = 0;
		for (int i = N - 1; i >= 0; i--) {
			sum += d[i][j];
			d[i][j] = sum;
		}
	}
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		cout << d[l][r] << endl;
	}
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define pr pair<int,int>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    #define bin(x) (1ll<<(x))
    #define GG(x) if(x) {puts("error");exit(666);}
    #define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
    #define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

    const int INF=0x3f3f3f3f;
    const int MOD=998244353;
    inline int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> inline void add(T &x,const T y){x=mm(x+y);}
    inline ll qpower(ll x,ll e,int mod=MOD){ll ans=1;GG(e<0);while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e6+10;

    const int MM=9;
    const int base[MM+1]={131,13331,131,13331,2333, 66666666,13331,131,13331,2333};
    const int mod[MM+1]={998244353,998244353,1000000007,993244853,1000000009,1000000007,998244353,993244853,993244853,998244353};
    struct Data
    {
        ll state[MM+1],bs[MM+1];
        Data(){fo(i,0,MM)state[i]=0,bs[i]=1;}
        friend bool operator < (Data x,Data y)
        {
            fo(i,0,MM) if(x.state[i]!=y.state[i]) return x.state[i]<y.state[i];
            return 0;
        }
        void insert(char c)
        {
            if(c=='+' or c=='-')
            {
                fo(i,0,MM) (state[i]+=bs[i]*(c=='+'?1:mod[i]-1) )%=mod[i];
            } else
            {
                fo(i,0,MM) (bs[i]*=(c=='>'?base[i]:qpower(base[i],mod[i]-2,mod[i])) )%=mod[i];
            }
        }
        void output()
        {
            fo(i,0,MM) printf("(%lld,%lld) ",state[i],bs[i]);
            puts("");
        }
    };
    Data merg(Data left,Data right)
    {
        fo(i,0,MM) (left.state[i]+=left.bs[i]*right.state[i])%=mod[i],(left.bs[i]*=right.bs[i])%=MOD;
        return left;
    }
    map<Data,int> mp;

    char str[N];
    void main()
    {
        int n=qread();scanf("%s",str+1);
        Data all;fo(i,1,n) all.insert(str[i]);mp[all]++;//all.output();
        ll ans=0;Data now;
        fo(r,1,n)
        {
            now.insert(str[r]);
            // now.output();
            ans+=mp[now];
            mp[merg(now,all)]++;
            // merg(now,all).output();
            // puts("");
        }write(ans);
    }
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 102016
import java.util.*;

public class Main{
    static int min(int a, int b, int c){
        if(a<b && a<c)
            return a;
        else if(b<c)
            return b;
        else
            return c;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int l1 = s1.length();
        int l2 = s2.length();
        int[][] dp = new int[l1+1][l2+1];

        //initialize
        for(int i1=0; i1<=l1; i1++){
            dp[i1][0] = i1;
        }
        for(int i2=0; i2<=l2; i2++){
            dp[0][i2] = i2;
        }

        for(int i1=1; i1<=l1; i1++){
            for(int i2=1; i2<=l2; i2++){
                int cost = (s1.charAt(i1-1) == s2.charAt(i2-1)) ? 0 : 1;
                dp[i1][i2] = min(dp[i1-1][i2-1]+cost, dp[i1-1][i2]+1, dp[i1][i2-1]+1);
            }
        }
        System.out.println(dp[l1][l2]);
    }
}



Measured memory_bytes: 30784
#include <iostream>
#include <cstring>
#include <cassert>
using namespace std;

const int mod = 1000000007; // assert mod is prime

template<int M>
struct Mint {
    int x;
    Mint() : x(0) {}
    Mint(int y) : x(y >= 0 ? y % M : M - (-y) % M) {}
    Mint &operator += (const Mint &rhs){ if((x += rhs.x) >= M) x -= M; return *this; }
    Mint &operator -= (const Mint &rhs){ if((x += M - rhs.x) >= M) x -= M; return *this; }
    Mint &operator *= (const Mint &rhs){ x = 1LL*x*rhs.x % M; return *this; }
    Mint &operator /= (const Mint &rhs){ x = (1LL*x*rhs.inv().x) % M; return *this; }
    Mint operator - () const { return Mint(-x); }
    Mint operator + (const Mint &rhs) const { return Mint(*this) += rhs; }
    Mint operator - (const Mint &rhs) const { return Mint(*this) -= rhs; }
    Mint operator * (const Mint &rhs) const { return Mint(*this) *= rhs; }
    Mint operator / (const Mint &rhs) const { return Mint(*this) /= rhs; }
    bool operator < (const Mint &rhs) const { return x < rhs.x; }
    Mint inv() const {
        signed a = x, b = M, u = 1, v = 0, t;
        while(b){ t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
        return Mint(u);
    }
    Mint pow(long long t) const {
        Mint e = *this, res = 1;
        for(; t; e *= e, t>>=1) if(t&1) res *= e;
        return res;
    }
};
template <int M>
ostream &operator << (ostream &os, const Mint<M> &rhs){
    return os << rhs.x;
}
template <int M>
istream &operator >> (istream &is, Mint<M> &rhs){
    long long s; is >> s; rhs = Mint<M>(s); return is;
};

using mint = Mint<mod>;

int N,C;
int a[410], b[410];
int vis[410][410];
mint dp[410][410];
mint power[410][410];

mint rec(int p, int rc){
    if(vis[p][rc]) return dp[p][rc];
    mint &res = dp[p][rc];
    if(p == N){
        res = rc == 0 ? 1 : 0;
    } else {
        res = 0;
        for(int c = 0; c <= rc; ++c){
            res += (power[b[p]+1][c] - power[a[p]][c]) * rec(p+1,rc-c);
        }
    }
    vis[p][rc] = true;
    return res;
}

int main(){
    while(cin >> N >> C){
        for(int i = 0; i <= 400; ++i){
            power[0][i] = 0;
            for(int j = 0; j <= 400; ++j){
                power[j+1][i] = power[j][i] + mint(j).pow(i);
            }
        }
        for(int i = 0; i < N; ++i) cin >> a[i];
        for(int i = 0; i < N; ++i) cin >> b[i];
        memset(vis, 0, sizeof vis);
        cout << rec(0,C) << endl;
    }
}



Measured memory_bytes: 2304
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
T = S()
print(T.replace('?', 'D'))

Measured memory_bytes: 68984
s = input()
a = [chr(i) for i in range(97, 97 + 26)]

if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

if len(s) != 26:
    print(s + sorted(list(set(a) - set(s)))[0])
else:
    j = 0
    for i in range(len(s) - 1):
        if s[i] < s[i + 1]:
            j = i
    x = []
    for i in s[j + 1:]:
        if s[j] < i:
            x.append(i)
    print(s[:j] + min(x))

Measured memory_bytes: 3064
import math
k = int(input())
s = 0
b = []
for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            p = len(set([i,j,l]))
            if p ==1:
                t = math.gcd(i,j)
                q = math.gcd(t,l)
                s += q
                b.append(q)
            elif p ==2:
                t = math.gcd(i,j)
                q = math.gcd(t,l)
                s += q*3
                b.append(q)
            else:
                t = math.gcd(i,j)
                q = math.gcd(t,l)
                s += q*6
                b.append(q)
print(s)

Measured memory_bytes: 19488
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


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

  Int n;
  cin>>n;

  if(n < 1000) cout<<"ABC"<<endl;
  else cout<<"ABD"<<endl;
  
  return 0;
}


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

#define ll long long
#define mod 1000000007
#define f(i, a, b) for (long long i = a; i < b; i++)
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define fm(i, a, b) for (long long i = a; i > b; i--)
#define repm(i, a, b) for (long long i = a; i >= b; i--)
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define pqmaxi priority_queue<int>
#define pqmaxl priority_queue<ll>
#define pqmini priority_queue<int, vi, greater<int>>
#define pqminl priority_queue<ll, vl, greater<ll>>
#define all(x) x.begin(), x.end()
#define test     \
    ll test;     \
    cin >> test; \
    while (test--)
#define pb(i) push_back(i)
#define mp(i, j) make_pair(i, j)
#define fast                     \
    ios::sync_with_stdio(false); \
    cin.tie(NULL)

int main()
{
    fast;
    ll n;
    cin >> n;
    vl v(n);
    f(i, 0, n)
    {
        cin >> v[i];
    }
    ll min1 = mod;
    ll max1 = -mod;
    f(i, 0, n)
    {
        min1 = min(min1, v[i]);
        max1 = max(max1, v[i]);
    }
    ll ans = mod;
    f(j, min1, max1 + 1)
    {
        ll cst = 0;
        f(i, 0, n)
        {
            cst += (v[i] - j) * (v[i] - j);
        }
        ans = min(ans, cst);
    }
    cout << ans;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=1;i<n;i++)
#define rf(i,n) for(int i=n-1;i>=0;i--)
#define rep(a,b,c) for(int i=a;i<b;i++)
#define repn(a,b,c) for(int i=a;i<=b;i++)
#define PI 3.1415926535897932384626433832795
#define fi first
#define se second
#define mp(x,y) make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define BIN(n,x) bitset<n>(x)  
#define mod (ll)1000000007
using namespace std;
typedef vector<ll> vl;
typedef vector<int> vi;

//nC2
ll C2(ll n){
    ll ans= max(((n*(n-1))/2),(ll)0);
    return ans;
}

//GCD
ll gcd(ll a,ll b){
    if(a<b){
        swap(a,b);
    }
    if(a%b==0){
        return b;
    }
    else{
        return gcd(b,a%b);
    }
}
//sort pair by second values
bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b){ 
    return (a.second < b.second); 
}


ll BinExp(ll a, ll b, ll m){
    a%=m;
    ll res =1;
    while(b>0){
        if(b&1){
            res = (res * a)%m;
        }
        a=(a*a)%m;
        b>>=1;
    }
    return res;
}


int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll a,b,n;
    ll x=0,x1=0,x2=0;
    cin>>a>>b>>n;

    if(n>=b){
        x=b-1;
    }
    else{
        x=n;
    }
    x1=(ll)((a*x)/b);
    x2=(ll)(x/b);
    ll x3=x1-a*x2;
    cout<<x3<<endl;


    return 0;
}



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

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

long long MOD = 1000000000 + 7;

int z_algorithm(string S){
  vector<int> A(S.size(),0);
  // zアルゴリズム 
  A[0] = S.size();
  int i = 1, j = 0;
  while (i < S.size()){
    while (i+j < S.size() && S[j] == S[i+j]) ++j; // 右向きにjを伸ばしていく
    A[i] = j;
    if (j == 0) { ++i; continue;}
    int k = 1;
    while (i+k < S.size() && k+A[k] < j) A[i+k] = A[k], ++k; // i~j間にkを走らせる
    i += k; j -= k;
  }

  int ret = 0; 
  for(int i = 0; i < S.size(); i++){
    int tmp = min(i, A[i]);
    ret = max(tmp, ret);
  }
  return ret;
}

int main(){
  cout << setprecision(10);

  int N; cin >> N;
  string S; cin >> S;

  int ret = 0;
  for(int l = 0; l < N; l++){
    string x = S.substr(l);
    int tmp = z_algorithm(x);
    ret = max(ret, tmp);
  }
  cout << ret << endl;
}


Measured memory_bytes: 3696
// "header" {{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod1 = 1000000007;
const long long mod2 = 998244353;


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

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){
    return ((n + d -1) / d);
}

inline int square(int a){ return a * a; }

inline double Sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

    xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	
    return xRes * x;
}

// }}}

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

    vector<vector<double> > dp(n+1,vector<double>(n+1));
    vector<double> p(n+1);

    reps(i,n){
        cin >> p[i];
    }

    dp[0][0] = 1;
    double res = 0;
    
    reps(i,n){
        rep(j,n+1){
            dp[i][j] = dp[i-1][j] * (1 - p[i]) + (j != 0 ? dp[i-1][j-1] * p[i] : 0);
        }
    }

    for(int i = n;i > n / 2;--i){
        res += dp[n][i];
    }

    cout << Fixed << res << '\n';
    
    return 0;
}


Measured memory_bytes: 70656
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
    int n;
    cin>>n;
    string s1,s2;
    cin>>s1>>s2;
    vector<int> v;
    rep(i,n){
        if(s1[i]==s2[i]){v.push_back(1);}
        else{
            v.push_back(2);
            i++;
        }
    }
    ll ans = 3;

    rep(i,v.size()){
        if(i==0){
            if(v[i]==2){
                ans*=2;
            }
        }else{
            if(v[i]==v[i-1]){
                if(v[i]==1){
                    ans*=2;
                }else{
                    ans*=3;
                }

                ans%=MOD;
            }else{
                if(v[i]==1){

                }else{
                    ans*=2;
                    ans%=MOD;
                }
            }
        }



    }
    cout<<ans<<endl;

    
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
long long int dp[100000];
long long int cost(long long int n,long long int k,vector<long long int>&arr)
{
    if(dp[n]!=-1)return dp[n];
    else
    {
        long long int min;
        for(long long int i=n-1;(i>=n-k)&&i>=0;i--)
        {
            long long int x;
            x=abs(arr[n]-arr[i])+cost(i,k,arr);
            if(i==n-1)min=x;
            if(min>x)min=x;
        }
        dp[n]=min;
    }
    return dp[n];
}
 
int main()
{
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    long long int n,k;
    cin>>n>>k;
    vector<long long int>arr(n);
    for(long long int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    dp[1]=abs(arr[1]-arr[0]);
    cout<<cost(n-1,k,arr);
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPP(i, n) for(int i = 1; i <= n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const ll MOD = 1000000007;

int main() {
    stack<int> s;
    string str;
    int a,b;
    while(cin >> str) {
        if(str=="+") {
            a = s.top(); s.pop();
            b = s.top(); s.pop();
            s.push(b+a);
        }
        else if(str=="-") {
            a = s.top(); s.pop();
            b = s.top(); s.pop();
            s.push(b-a);
        }
        else if(str=="*") {
            a = s.top(); s.pop();
            b = s.top(); s.pop();
            s.push(b*a);
        }
        else s.push(stoi(str));
    }
    cout << s.top() << endl;
    return 0;
}


Measured memory_bytes: 3152
#include <algorithm>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


using namespace std;


class Solution {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n, k;
    in >> n >> k;
    int ar[n];
    for (int ctr1 = 0; ctr1 < n; ++ctr1)
      in >> ar[ctr1];
    sort(ar, ar + n);
    int rez = ar[k - 1] - ar[0];
    for (int ctr1 = 0; ctr1 + k <= n; ++ctr1)
      rez = min(ar[ctr1 + k - 1] - ar[ctr1], rez);
    out << rez;
  }
};

void solve(std::istream& in, std::ostream& out)
{
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}
// Powered by caide (code generator, tester, and library code inliner)


#include <fstream>
#include <iostream>


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


  istream& in = cin;


  ostream& out = cout;

  solve(in, out);
  return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int inf = 2e18;
const int mod = 1e9 + 7;

signed main() {
    int N;
    cin >> N;
    vector<int> A(N);
    cin >> A;
    deque<int> color;
    for (int a : A) {
        auto itr = lower_bound(color.begin(), color.end(), a);
        if (itr == color.begin()) {
            color.push_front(a);
        } else {
            *(itr - 1) = a;
        }
    }
    cout << color.size() << endl;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
 
namespace IO{
    const int insiz = 1 << 12, outsiz = 1 << 18;
    char in[insiz], *A(in), *B(in); char out[outsiz], *ptr(out);
    inline char getc(){
    	#ifndef LOCAL
        return (A == B) && (B = (A = in) + fread(in, 1, insiz, stdin), A == B) ? EOF : *A++;
        #endif
        return getchar();
    }
    template <typename T> inline T read(){
        T ret(0), p(1); char ch(getc());
        while(ch < '0' || ch > '9'){
            if(ch == '-') p = -1; ch = getc();
        }
        while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getc();
        return ret*p;
    }
    inline void flush(){ fwrite(out, 1, ptr - out, stdout); ptr = out; }
    template <typename T> inline void write(T x, char cmd = '\n'){
        if(x < 0) *ptr++ = '-', x = -x;
        if(x == 0) *ptr++ = '0';
        static char s[123]; int cnt = 0;
        for(; x; x /= 10) s[++cnt] = x % 10 + '0';
        for(; cnt; --cnt) *ptr++ = s[cnt];
        *ptr++ = cmd;
        if((outsiz >> 1) > ptr - out) flush();
    }
} using IO::getc; using IO::read; using IO::write; using IO::flush;
 
char s[1123][1123]; 
bool mp[1123][1123];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int n, m;
inline bool inarea(int x, int y){
	return x > 0 && x <= n && y > 0 && y <= m;
} 
int main(){
	std::queue<std::pair<int, int> > q;
	scanf("%d%d", &n, &m);
	bool zero(true);
	for(int i(1); i <= n; ++i){
		scanf("%s", s[i] + 1);
		for(int j(1); j <= m; ++j){
			if(s[i][j] == '#'){
				mp[i][j] = true;
				q.push(std::make_pair(i, j));
			}
			else zero = false;
		}
	}
	int ans(-1);
	while(!q.empty()){
		int len = q.size();
		while(len--){
			int nx = q.front().first, ny = q.front().second;
			q.pop();
			for(int i(0); i < 4; ++i){
				int tx = nx + dx[i], ty = ny + dy[i];
				if(!mp[tx][ty] && inarea(tx, ty)){
					mp[tx][ty] = true;
					q.push(std::make_pair(tx, ty));
				}
			}
		}
		++ans;
	}	
	write(ans);
	flush(); return 0;
}
 
 

Measured memory_bytes: 10640
N = int(input())
table = []
for i in range(N):
    tmp = list(input().split())
    tmp[1] = int(tmp[1]) * (-1)
    tmp_table = [tmp, i+1]
    table.append(tmp_table)
table.sort()
for i in range(N):
    print(table[i][1]) 

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

void solve() {
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int x;
	cin >> x;
	if (x)
		cout << 0 << "\n";
	else
		cout << 1 << "\n";
	
	return 0;
}


Measured memory_bytes: 3608
n,k,q=(int(x) for x in input().split())
a=[]
p=[0]*n
for i in range(0,q):
    temp=int(input())
    p[temp-1]+=1
border=-k+q

res = '\n'.join('Yes' if p[j]> border else 'No' for j in range(0,n))

print(res)


Measured memory_bytes: 5028
/*
 * @Author: Kaustav Vats  
 */
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;


class Main {

    public static void PrintIntArray(int[] Arr) {
        for (int i=0; i<Arr.length; i++) {
            System.out.print(Arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException{
        Reader.init(System.in);
        int N = Reader.nextInt();
        long[] Arr = new long[N+1];
        long[] Brr = new long[N];
        for (int i=0; i<=N; i++) {
            Arr[i] = Reader.nextLong();
        }
        for (int i=0; i<N; i++) {
            Brr[i] = Reader.nextLong();
        }
        long count = 0;
        int i = 0;
        
        while(i < N) {
            if (Arr[i] < Brr[i]) {
                count += Arr[i];
                Brr[i] -= Arr[i];
                Arr[i] = 0;
                if (Arr[i+1] > Brr[i]) {
                    count += Brr[i];
                    Arr[i+1] -= Brr[i];
                }
                else {
                    count += Arr[i+1];
                    Brr[i] -= Arr[i+1];
                    Arr[i+1] = 0;
                }
            }
            else {
                count += Brr[i];
                Brr[i] = 0;
            }
            i++;
        }
        System.out.println(count);
    }
}


/** Class for buffered reading int and double values */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

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

    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
	
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}

Measured memory_bytes: 42844
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int main(void){
    string S;
    cin >> S;
    int L=S.length();
    string ans;
    rep(i,L){
        if(S[i]=='0') ans+='0';
        if(S[i]=='1') ans+='1';
        if(S[i]=='B' && !ans.empty())ans.pop_back();
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    if(s[0]!=s[1]||s[0]!=s[2]||s[1]!=s[2]){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <complex>
#include <algorithm>
#include <cfloat>
using namespace std;

const double EPS = 1e-6;

typedef complex<double> P;

double cross(P va, P vb){
	return real(va) * imag(vb) - imag(va) * real(vb);
}

double distanceLP(P a, P b, P c){
	return abs(cross(b - a, c - a)) / abs(b - a);
}

P crosspoint(P pa1, P pa2, P pb1, P pb2){
	P da12 = pa2 - pa1;
	P db21 = pb1 - pb2;
	P dab1 = pb1 - pa1;
	double d = cross(da12, db21);
	if(abs(d) > EPS){
		double t = cross(dab1, db21) / d;
		return pa1 + t * da12;
	}
	return P(DBL_MAX, DBL_MAX);
}

int main(){
	int n;
	P pts[110];
	double x, y;
	while(scanf("%d", &n), n){
		for(int i = 0; i < n; ++i){
			scanf("%lf%lf", &x, &y);
			pts[i] = P(x, y);
		}
		pts[n] = pts[0];
		
		double ans = 0.0;
		for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
		for(int k = j + 1; k < n; ++k){
			int e0 = i, e1 = j, e2 = k;

			if(abs(cross(pts[i + 1] - pts[i], pts[j + 1] - pts[j])) < EPS){
				e0 = j;
				e1 = k;
				e2 = i;
			}
			else if(abs(cross(pts[j + 1] - pts[j], pts[k + 1] - pts[k])) < EPS){
				e0 = k;
				e1 = i;
				e2 = j;
			}

			P tmp[4];
			tmp[0] = pts[e0];
			tmp[1] = crosspoint(pts[e0], pts[e0 + 1], pts[e1], pts[e1 + 1]);
			tmp[2] = crosspoint(pts[e1], pts[e1 + 1], pts[e2], pts[e2 + 1]);
			tmp[3] = pts[e2 + 1];
			double a1 = 0.5 * (arg(tmp[2] - tmp[1]) + arg(tmp[0] - tmp[1]));
			double a2 = 0.5 * (arg(tmp[3] - tmp[2]) + arg(tmp[1] - tmp[2]));
			P c = crosspoint(tmp[1], tmp[1] + polar(1.0, a1), tmp[2], tmp[2] + polar(1.0, a2));
			if(real(c) == DBL_MAX){ continue; }
			double d = distanceLP(pts[j], pts[j + 1], c);
			if(d <= ans){ continue; }
			bool ok = true;
			for(int h = 0; h < n && ok; ++h){
				if(distanceLP(pts[h], pts[h + 1], c) < d - EPS){
					ok = false;
				}
				if(cross(pts[h + 1] - pts[h], c - pts[h]) < -EPS){
					ok = false;
				}
			}
			if(ok){
				ans = d;
			}
		}
		printf("%.9f\n", ans);
	}
}

Measured memory_bytes: 1340
// // If you want something you've never had, you must be willing to do
// // something you've never done

// //  When the going gets tough,  the tough get going

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

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

using namespace std;
using namespace __gnu_pbds;

typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<pair<int,int>, null_type,less<pair<int, int> >,rb_tree_tag,tree_order_statistics_node_update > pbds;

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#define ROUNDOFFINT(d) d = (int)((double)d + 0.5)
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define pb push_back
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// #define int ll
ll power(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while(b) {
        if(b % 2) {
            res *= a;
            res %= mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}
const int INF = 2e9;

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



signed main() {
    int n; cin >> n;
    set<string> s;
    string x;
    for(int i=1; i<=n; i++) {
        cin >> x;
        s.insert(x);
    }
    cout << (int)s.size() << '\n';
    return 0;
}


Measured memory_bytes: 19208
#include <bits/stdc++.h>
using namespace std;
int fun(int x)
{
  if(x==0)
  {
    return 1;
  }
  else
    return 2*fun(x-1);
}
int main() {
   int n,m;
   int ans=0;
   cin>>n>>m;
   ans=fun(m)*(m*1900+(n-m)*100);
   cout<<ans<<endl;
  return 0;
}


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

int main(void){

  char S[100];
  scanf("%s", S);

  long long K;
  scanf("%lld\n", &K);


  int i=0;

  while(i<K){
    if(S[i]!='1'){
      printf("%c\n", S[i]);
      return 0;
    }else{
      i++;
    }
  }

  printf("1\n");
  return 0;

 }



Measured memory_bytes: 128
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1;c+=m-l-i
 return c
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  return s(A,l,m)+s(A,m,r)+g(A,l,m,r)
 else:return 0
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(c)


Measured memory_bytes: 27480
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

set<pi> s;

int main()
{
	int n,ans = 0;
	cin >> n;

	rep(i, n) {
		int a;
		cin >> a;
		if (i + 1 > a)s.insert({ i + 1, a });
		else s.insert({ a,i + 1 });
	}
	cout << n - s.size() << endl;
	return	0;
}




Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <set>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll bit[100010], num;
ll n, par[100010], k, kai[2010];

ll sum(ll i)
{
	ll s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(ll i, ll x)
{
	while (i <= num)
	{
		bit[i] += x;
		i += i & -i;
	}
}

ll po(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2)
	{
		return po(x, y - 1) * x % mod;
	}
	else
	{
		ll yyy = po(x, y / 2);
		return yyy * yyy % mod;
	}
}

ll div(ll x)
{
	return po(x, mod - 2);
}

int main(void)
{
	cin >> n >> k;
	kai[0] = 1;
	for (int i = 1; i <= 2005; i++)
	{
		kai[i] = kai[i - 1] * i % mod;
	}
	for (ll i = 1; i <= k; i++)
	{
		if (k < i || n - k + 1 < i)
		{
			cout << 0 << endl;
			continue;
		}
		ll ans = kai[k - 1] * div(kai[i - 1]) % mod * div(kai[k - i]) % mod;
		(ans *= kai[n - k + 1] % mod * div(kai[i]) % mod * div(kai[n - k + 1 - i]) % mod) %= mod;
		cout << ans << endl;
	}
	int www;
	cin >> www;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int NUM=1e5+1;

int main(){
  int N, M;
  cin >> N >> M;
  int Y[NUM];
  int P[NUM];
  vector<int> C[NUM];
  for(int i=1; i<=M; i++){
    cin >> P[i] >> Y[i];
    C[P[i]].push_back(Y[i]);
  }
  for(int i=1; i<=N; i++){
    sort(C[i].begin(), C[i].end());
  }
  for(int i=1; i<=M; i++){
    cout << setw(6) << setfill('0') << P[i];
    auto pos = lower_bound(C[P[i]].begin(), C[P[i]].end(), Y[i]);
    int idx = (int)distance(C[P[i]].begin(), pos)+1;
    cout << setw(6) << setfill('0') << idx << endl;
  }
  return 0;
}

Measured memory_bytes: 7808
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int a[3][3]; bool check[3][3] = {};
  rep(i, 3){
    rep(j, 3){
      cin >> a[i][j];
    }
  }
  int N; cin >> N;
  rep(i, N){
    int t; cin >> t;
    rep(j, 3){
      rep(k, 3){
        if(a[j][k]==t) check[j][k]=true;
      }
    }
  }
  bool ans = false, can= true;
  rep(i, 3){
    can = true;
    rep(j, 3){
      if(!check[i][j]) can=false;
    }
    if(can) ans=true;
  }
  rep(j, 3){
    can = true;
    rep(i, 3){
      if(!check[i][j]) can=false;
    }
    if(can) ans = true;
  }
  can = true;
  rep(i, 3){
    if(!check[i][i]) can=false;
  }
  if(can) ans=true;
  can=true;
  rep(i, 3){
    if(!check[i][2-i]) can=false;
  }
  if(can) ans=true;
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

const long long mod = 1e9 + 7;

int main() {
    
    
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    vector<ll> kv;
    for (int i = 0; i < n; ++i)
    {
        ll c = a[i];
        for (int j = i + 1; j < n; ++j)
        {
            kv.push_back(c);
            c += a[j];
        }
        kv.push_back(c);
    }
    sort(kv.begin(), kv.end());
    ll ret = 0;
    for (int d = 63; d >= 0; --d)
    {
        ll count = 0;
        ll num = 1ll << d;
        ll next = ret + num;
        
        for (int i = 0; i < kv.size(); ++i)
        {
            if ((next & kv[i]) == next)
            {
                count++;
            }
        }
        if (count >= k)
        {
            ret += num;
        }
    }
    
    cout << ret << endl;
    
    
    return 0;
}

Measured memory_bytes: 6516
#include <iostream>
#include <vector>
#include <cstdlib>  
#include <algorithm>
#include <string>
#include <math.h>                                                               
#include <stdio.h>   
using namespace std;
 
int main() {
    int n;cin>>n;
    int a[n][15];//嘘つき０正直１
    for(int i= 0;i<n;i++)for(int j=0;j<15;j++) a[i][j] = -1;
    for(int i = 0;i<n;i++){
      int aa;cin>>aa;
      for(int j = 0;j<aa;j++){
       int x,y;cin>>x>>y;
       if(y == 1) a[i][x-1]=1;
       else a[i][x-1] = 0;
      }
    }
    int saidai = 0;
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> S;
        int syo[n];
        for(int i= 0;i<n;i++) syo[i] = 0;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                S.push_back(i);
            }
        }
        for (int i = 0; i < (int)S.size(); ++i) {
            syo[S[i]] = 1;
        }
        int dame = 0;
        bool usotuki = false;
        for (int i = 0; i < (int)S.size(); ++i) {
          for(int j = 0;j < 15;j++){
               int b = a[S[i]][j];
               if(b == -1) continue;
               int dou = 0;
               if(b == 1) dou = 1;
               if(b == 0) dou = 0;
               if(dou != syo[j]){
                 usotuki = true;
                 break;
               }
           }
          if(usotuki){
            dame = 1;
            break;
          }
        }
        if(dame == 0) saidai = max((int)S.size(),saidai);
    }
    cout<<saidai;
    return 0;
}

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

constexpr int64_t mod = 998244353;
template<typename Tp>
class binary_indexed_tree{
    vector<Tp> tree;
    int depth;

public:
    binary_indexed_tree(size_t n){
        for(depth=0;(1<<depth)<n;depth++);
        tree.resize(1ULL<<depth);
    }

    void add(size_t pos, Tp value){
        pos++;
        for(;pos<=(1<<depth);pos+=pos&-pos){
            tree[pos-1] += value;
        }
    }

    Tp sum(size_t pos){
        pos++;
        int64_t s = 0;
        for(;pos>0;pos-=pos&-pos){
            s += tree[pos-1];
        }

        return s;
    }

    Tp sum(size_t left, size_t right){
        return sum(right-1) - sum(left-1);
    }
};

int64_t mpow(int64_t x, int64_t y){
    if(y == 0) return 1;
    if(y == 1) return x % mod;
    if(y%2 == 0) return mpow(x*x%mod, y/2);
    return mpow(x*x%mod, y/2) % mod * x % mod;
}

int main(){
    int n;
    cin >> n;
    pair<int,int> pts[200000];
    for(int i=0;i<n;i++){
        int x, y;
        cin >> x >> y;
        pts[i] = {x, y};
    }
    sort(pts, pts+n, [](const auto& x, const auto& y){ return x.second < y.second; });
    for(int i=0;i<n;i++) pts[i].second = i;
    sort(pts, pts+n);
    for(int i=0;i<n;i++) pts[i].first = i;
    
    binary_indexed_tree<int> bit_y(n);
    int ul[200000] = {0};
    for(int i=0;i<n;i++){
        ul[i] = i - bit_y.sum(pts[i].second);
        bit_y.add(pts[i].second, 1);
    }

    int64_t ans = 0;
    for(int i=0;i<n;i++){
        int64_t a, b, c, d;
        a = ul[i];  b = n - bit_y.sum(pts[i].second) - a;
        c = i - a;  d = n - (a + b + c) - 1;
        ans = (ans + mpow(2, a) + mpow(2, b) + mpow(2, c) + mpow(2, d) - 3) % mod;
        ans = (ans + (mpow(2, a) - 1) * (mpow(2, b) - 1) % mod + (mpow(2, b) - 1) * (mpow(2, d) - 1) % mod + 
            (mpow(2, d) - 1) * (mpow(2, c) - 1) % mod + (mpow(2, c) - 1) * (mpow(2, a) - 1) % mod) % mod;
        ans = (ans + 2 * (mpow(2, a) - 1) * (mpow(2, d) - 1) % mod * mpow(2, b) % mod * mpow(2, c) % mod +
            2 * (mpow(2, b) - 1) * (mpow(2, c) - 1) % mod * mpow(2, a) % mod * mpow(2, d) % mod -
            2 * (mpow(2, a) - 1) * (mpow(2, d) - 1) % mod * (mpow(2, b) - 1) % mod * (mpow(2, c) - 1) % mod + mod) % mod;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584
program abc159b
  implicit none
  integer :: i, l
  character :: a, b, c
  character(3) :: ans = 'Yes'
  character(100) :: s
  read *, s
  l = len_trim(s)
  do i = 1,l/2
     a = s(i:i)
     b = s(l+1-i:l+1-i)
     c = s(l/2+1+i:l/2+1+i)
     if (a/=b.or.a/=c) then
        ans = 'No'
        exit
     end if
  end do
  print *, ans
end program abc159b


Measured memory_bytes: 384
#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;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define LLINF (1e18)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int calc(pair<int, int> a, pair<int, int> b)
{
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w, d;
    cin >> h >> w >> d;
    // vector<vector<int>> a(h, vector<int>(w));
    vector<pair<int, int>> mp(h * w + 1);
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            int a;
            cin >> a;
            mp[a] = make_pair(i, j);
        }
    }

    vector<int> cost(h * w + 1, 0);

    for (int i = 1; i <= h * w; i++)
    {
        if (i <= d)
        {
            cost[i] = 0;
        }
        else
        {
            cost[i] = cost[i - d] + calc(mp[i - d], mp[i]);
        }
    }

    int q;
    cin >> q;
    for (int query = 0; query < q; query++)
    {
        int left, right;
        cin >> left >> right;
        int res = cost[right] - cost[left];
        cout << res << endl;
    }
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
const ll INF = 1LL<<60;
const int INT_INF = 1e9;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
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; }
using namespace std;

int N, K;

int main() {
    cin >> N >> K;
    rep(i, N) {
        int a; cin >> a;
    }
    int ans = ceil((N - 1.0) / (K - 1.0));
    cout << ans << endl;
}


Measured memory_bytes: 256
def binarySearch(key, arr, N):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return 1
        elif key < arr[mid]:
            right = mid
        else:
            left = mid + 1
    return 0


N1 = int(input())
arr1 = [int(n) for n in input().split()]
N2 = int(input())
arr2 = [int(n) for n in input().split()]

print(sum([binarySearch(key, arr1, N1) for key in arr2]))



Measured memory_bytes: 16892
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
struct UnionFind {
  vector<int> data;
  vector<int> sum;
  UnionFind(int v) : data(v, -1), sum(v, 0) {}
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (size(y) > size(x))
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
      sum[x] += sum[y];
    }
  }
};
struct Edge {
  int a, b, cost;
  Edge(int a_, int b_, int cost_) : a(a_), b(b_), cost(cost_) {}
  bool operator <(const Edge &other) const {
    return this->cost < other.cost;
  }
};
signed main() {
  ios::sync_with_stdio(false);
  int caseNumber = 1;
  while(true) {
    int N, T, K; cin >> N >> T >> K;
    if(N == 0 && T == 0 && K == 0) break;
    vector<Edge> G;
    REP(i, N - 1) {
      int a, b, cost; cin >> a >> b >> cost;
      --a, --b;
      G.emplace_back(a, b, cost);
    }
    vector<int> B(T);
    REP(i, T) {
      cin >> B[i];
      B[i]--;
    }
    sort(G.rbegin(), G.rend());
    int totalCost = 0;
    for(const auto &e : G) {
      totalCost += e.cost;
    }
    UnionFind uf(N);
    for(int b : B) {
      uf.sum[b] = 1;
    }
    int mergeCount = 0;
    int mergeCost = 0;
    for(const auto &e : G) {
      if (uf.sum[uf.root(e.a)] == 0 || uf.sum[uf.root(e.b)] == 0) {
        mergeCost += e.cost;
        uf.merge(e.a, e.b);
      }
      else if(mergeCount < T - 1 - K) {
        mergeCount++;
        mergeCost += e.cost;
        uf.merge(e.a, e.b);
      }
    }
    int ans = totalCost - mergeCost;
    cout << "Case " << caseNumber << ": " << ans << endl;
    caseNumber++;
  }
}

Measured memory_bytes: 3564