akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

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

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

	qsort(hei, 10, sizeof(int), comp);

	for(i=0;i<3;i++){
		printf("%d\n", hei[i]);
	}
	return 0;
}

Measured memory_bytes: 604
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double PI = (double)acos(-1);
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  string b;
  cin >> b;

  int ans, x;
  ans = x = 0;
  for (int i = 0; i < b.size(); i++) {
    if (b[i] == 'A' || b[i] == 'G' || b[i] == 'C' || b[i] == 'T') {
      x++;
      chmax(ans, x);
    } else {
      x = 0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　 |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



int A, B, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;

    int ans = 0;
    chmax(ans, A * 10 + B + C);
    chmax(ans, B * 10 + A + C);
    chmax(ans, C * 10 + A + B);
    cout << ans << endl;
}

Measured memory_bytes: 256
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")

//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

// -------------------</optimizations>--------------------
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define d long double
#define pii pair<int,int>
#define pb push_back
#define pf push_front
#define cases int tc;cin>>tc;while(tc--)
#define N 100003
#define M 103
#define inf LLONG_MAX
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//int mod=1e9+7;
//int mod=998244353;

signed main()
{
    SPEED

    int r,d,x;
    cin>>r>>d>>x;
    int i,ans;
    for(i=1;i<=10;++i)
    {
        ans=(r*x-d);
        x=ans;
        cout<<ans<<'\n';
    }
    
    
    return 0;
}


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

int main(){
  int N;
  cin>>N;
  int P[N];
  for(int i=0;i<N;i++)cin>>P[i];
  
  int minval=200010;
  int ans=0;
  
  for(int i=0;i<N;i++){
    if(P[i]<=minval){
      ans++;
      minval=P[i];
    }
  }
  cout<<ans<<endl;
}
  

Measured memory_bytes: 1024
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
S = input()

while len(S) >= 5:
    # Sを４つの単語で順に調べて刈っていく
    if len(S) >= 7 and S[-7:] == "dreamer":
        S = S[:-7]
        continue

    if len(S) >= 6 and S[-6:] == "eraser":
        S = S[:-6]
        continue

    elif S[-5:] == "dream" or S[-5:] == "erase":
        S = S[:-5]
        continue

    else:
        break

if len(S) == 0:
    print("YES")
else:
    print("NO")

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

constexpr int MAX_N = 200;
int divi[MAX_N + 1];

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

  for (int i{3}; i <= N; i += 2) {
    for (int j{1}; j <= i; j += 2) {
      if (i % j == 0)
        ++divi[i];
    }
  }
  int ans{};
  for (int i{3}; i <= N; ++i)
    if (divi[i] == 8)
      ++ans;

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


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

int main(){
    int N;
    string S;
    cin >> N >> S;
    vector<int> cnt(26);
    for(int i=0;i<N;i++){
        cnt[S[i]-'a']++;
    }
    bool judge = false;
    for(int i=0;i<26;i++) if(cnt[i]>1) judge = true;
    if(!judge){
        cout << 0 << endl;
        return 0;
    }
    auto prekmp = [&](string x,int m,vector<int>& kmpnext){
        int i = 0,j = kmpnext[0] = -1;
        while(i<m){
            while(j>-1 && x[i]!=x[j]) j = kmpnext[j];
            i++; j++;
            if(x[i]==x[j]) kmpnext[i] = kmpnext[j];
            else kmpnext[i] = j;
        }
    };
    auto KMP = [&](string x,int m,string y,int n){
        vector<int> kmpnext(m+1);
        int i = 0,j = 0;
        prekmp(x,m,kmpnext);
        while(j<n){
            while(i>-1 && x[i]!=y[j]) i = kmpnext[i];
            i++; j++;
            if(i>=m){
                i = kmpnext[i];
                return true;
            }
        }
        return false;
    };
    auto ok = [&](int len){
        bool res = false;
        for(int i=0;i<=N-2*len;i++){
            string now = S.substr(i,len);
            string ne = "";
            for(int j=i+len;j<N;j++) ne += S[j];
           // cerr << now << " " << ne << endl;
            if(len>ne.size()) continue;
            res |= KMP(now,now.size(),ne,ne.size());
            //cerr << now << " " << ne << endl;
            if(res) return res;
        }
        return res;
    };
    int l = 0,r = N;
    while(l+1<r){
        int m = (l+r)/2;
//        cerr << m << endl;
        if(ok(m)) l = m;
        else r = m;
//        cerr << m << endl;
    } 
    cout << l << endl;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cmath>
int main(){
    int hos,ang;
    int t=90;
    double x=0,y=0;
    for(;;){
        scanf("%d,%d",&hos,&ang);
        if(hos==0 && ang ==0) break;
        x+=hos*cos(t*M_PI/180);
        y+=hos*sin(t*M_PI/180);
        t-=ang;
    }
    printf("%d\n%d\n",(int)x,(int)y);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 100010;
int n, m, a, b, ans = 0;
pii p[N];
set<int> s;
int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) scanf("%d%d", &a, &b), p[i] = {b, a};
    for(int i = 1; i <= m; i++) s.insert(i);
    s.insert(1000000);
    sort(p, p+n);
    for(int i = n-1; i > -1; i--) {
        int t = *s.lower_bound(p[i].second);
        if(t != 1000000) {
            s.erase(t);
            ans += p[i].first;
        }
    }
    cout << ans;
}

Measured memory_bytes: 5760
#include <iostream>
#include <string>
#include <map>

using namespace std;

map<string, int> table;

int main() {
  string word, frequent, longest;
  size_t N = 0; // size_t represents size in bytes of word (length)
  while (cin >> word) {
    table[word] += 1;
    if (table[word] > N) {
      N = table[word];
      frequent = word;
    }
    if (word.size() > longest.size()) longest = word;
  }
  cout << frequent << " " << longest << endl;
}

Measured memory_bytes: 1196
#include<iostream>
int main()
{
	int cnt[26];
	for(int i = 0; i < 26; i++)cnt[i] = 0;
	while(true)
	{
		char c;
		std::cin >> c;
		if(std::cin.eof())
		{
			break;
		}
		else if('A' <= c && c <= 'Z')
		{
			cnt[c - 'A']++;
		}
		else if('a' <= c && c <= 'z')
		{
			cnt[c - 'a']++;
		}
	}
	for(int i = 0; i < 26; i++)
	{
		std::cout << (char)(i + 'a') << " : " << cnt[i] << std::endl;
	}
	return 0;
}


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

int n, v[3];
vector<int> l;

int bfs(int flag, int d, int sum) {
    if (d == 3) {
        return sum;
    }

    int res = 1 << 28;
    for (int i = 1; i < (1 << n); i++) {
        if ((i & flag) != flag) continue;

        int ch = i - flag;

        if (ch <= 0) continue;

        int count = 0;
        int s = 0;
        for (int j = 0; j < n; j++) {
            if (ch & (1 << j)) {
                s += l[j];
                count++;
            }
        }

        int sub = (count - 1)* 10 + abs(s - v[d]);

        res = min(res, bfs(i, d+1, sum + sub));
    }

    return res;
}

int main() {
    cin >> n >> v[0] >> v[1] >> v[2];
    l.resize(n);
    for (auto& i : l) cin >> i;

    cout << bfs(0, 0, 0) << endl;

    return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
l, r = map(int, input().split())
maxL = l
minR = r
for i in range(m-1):
  l, r = map(int, input().split())
  if maxL < l:
    maxL = l
  if minR > r:
    minR = r
    
ans = min(minR, n)
if ans - maxL+1 > 0:
  print(ans - maxL+1)
else:
  print(0)

    
  

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

int main(){
    int x,y,z;
    cin>>x>>y>>z;
    if(x>=y and x>=z){
        cout<<10*x+y+z<<endl;
    }else if(y>=x and y>=z){
        cout<<10*y+x+z<<endl;
    }else{
        cout<<10*z+x+y<<endl;
    }
    return 0;
}


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

ll ans = 0;
int n;
string s;
bool flag = false;
void solve(ll curr, ll j)
{
    if(curr == n)
    {
        ans+=j;
        return;
    }
    ll sum = 0;
    for(int i = curr; i<n; i++)
    {
        sum = (10*sum) + (s[i] - '0');
        solve(i + 1, j + sum);
    }
}
int main ()
{
    cin>>s;
    n = s.size();
    solve(0, 0);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string A, B;
  int ans;
  cin >> A >> B;
  if(A.at(0) == B.at(2)) {
    ans++;
  }
  if(A.at(1) == B.at(1)) {
    ans++;
  }
  if(A.at(2) == B.at(0)) {
    ans++;
  }
  if(ans == 3) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 3644
N,M,X = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

li = [0]*(N+1)
for i in range(1,N+1):
    if(i in A):
        li[i]=li[i-1]+1
    else:
        li[i]=li[i-1]
print(min(li[X]-0,li[-1]-li[X]))


Measured memory_bytes: 3060
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

template<class T>
class bit : public vector<T> {
private:
    lli n;
public:
    bit():vector<T>(){}
    bit(lli n):vector<T>(n+1,0){
        this->n = n;
    }
    T sum(lli i){
        T s = 0;
        for(;i > 0;i -= i & -i) s += this->at(i);
        return s;
    }
    void add(lli i,T x){
        for(;i <= n;i += i & -i) this->at(i) += x;
    }
};

bit<lli> b;

lli n,q;
lli c,s,t,x;

int main(){
    cin >> n >> q;
    b = bit<lli> (n+1);
    for(lli i = 0;i < q;i++){
        cin >> c;
        if(c == 0){
            cin >> s >> t >> x;
            b.add(s,x);
            b.add(t+1,-x);
        }else if(c == 1){
            cin >> x;
            cout << b.sum(x) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3616
# include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	swap(a, b);
	swap(a, c);
	cout << a << ' ' << b << ' ' << c << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <map>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string disp(bool x){
    return x ? "Yes" : "No";
}

int main(){
    double n,m,d; cin >> n >> m >> d;
    
    if(d==0) cout << fixed << setprecision(6) <<  (m-1)/n << endl;
    else cout << fixed << setprecision(6) <<  2*(n-d)*(m-1)/n/n << endl;
}







Measured memory_bytes: 384
import math

a, b, x = [int(x) for x in input().split()]

bootle_volume = a * a * b
half_bootle_volume = 0.5 * bootle_volume

res = 0
if half_bootle_volume == x:
    res = math.degrees(math.atan(1))
elif half_bootle_volume > x:
    y = a - ((2 * x) / (a * b))
    degree = math.degrees(math.atan((a - y) / b))
    res = 90 - degree
elif half_bootle_volume < x:
    y = ((2 * x) / (a ** 2)) - b
    if y == b:
        res = 0
    else:
        degree = math.degrees(math.atan(a / (b - y)))
        res = 90 - degree

print(res)


Measured memory_bytes: 3064
/*
我的心脏怦怦跳，监管者就在附近
*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<string>
#include<iostream>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<unistd.h>
#include<stdio.h>
#include<cstring>
#define random(a,b) (rand()%(b-a+1)+a)
using namespace std;
bool prime(int x){
	 int i;
	 if(x<2) return 0;
	 for(i=2;i*i<=x;i++){
		if(x%i==0){return 0;}
	 }
	 return 1;
}
int main()
{
	int n,h,s=0,p;
	cin>>n>>h;
	int i;
	for(i=0;i<n;i++){
		cin>>p;
		if(p>=h){
			s++;
		}
	}
	cout<<s;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int main()
{
	string s;
	cin >> s;
	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] == 'A'&&s[i + 1] == 'C')
		{
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
}

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

using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i, x) for(int i=0;i<(int)(x);i++)
#define REPS(i, x) for(int i=1;i<=(int)(x);i++)
#define RREP(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i, x) for(int i=((int)(x));i>0;i--)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i, c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &t) {
    os << "[";
    FOR(it, t) {
        if (it != t.begin()) os << ",";
        os << *it;
    }
    os << "]";
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const set<T> &t) {
    os << "{";
    FOR(it, t) {
        if (it != t.begin()) os << ",";
        os << *it;
    }
    os << "}";
    return os;
}

template<class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &t) { return os << "(" << t.first << "," << t.second << ")"; }

template<class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
    return pair<S, T>(s.first + t.first, s.second + t.second);
}

template<class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) {
    return pair<S, T>(s.first - t.first, s.second - t.second);
}

const int INF = 1 << 28;
const double EPS = 1e-8;
const int MOD = 1000000007;

int n, m;

int main(int argc, char *argv[]) {
    cin >> n;
    vi w(n), b(n);
    vector<vi> wl(2 * n, vi(n + 1)), bl(2 * n, vi(n + 1));
    REP(i, 2 * n) {
        char c;
        int x;
        cin >> c >> x;
        x--;
        if (c == 'W') w[x] = i;
        else b[x] = i;
        REP(j, i + 1) {
            (c == 'W' ? wl : bl)[j][x + 1] ++;
        }
    }
    REP(i, 2 * n) {
        REP(j, n) {
            wl[i][j + 1] += wl[i][j];
            bl[i][j + 1] += bl[i][j];
        }
    }
    vector<vi> dp(n + 1, vi(n + 1, MOD));
    dp[0][0] = 0;

    REP(i, n + 1) {
        REP(j, n + 1) {
            if (i < n) {
                chmin(dp[i+1][j], dp[i][j] + wl[w[i]][i] + bl[w[i]][j]);
            }
            if (j < n) {
                chmin(dp[i][j+1], dp[i][j] + wl[b[j]][i] + bl[b[j]][j]);
            }
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}


Measured memory_bytes: 78848
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll n,k;
	cin>>n>>k;
	ll w[n],v[n];
	for(int i=0;i<n;i++)
	{
		cin>>w[i];
		cin>>v[i];
	}
	ll dp[n+1][k+1];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=k;j++)
		{  //cout<<dp[i][j]<<" ";
			if(j-w[i]>=0)
				dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j]);
			else
				dp[i+1][j]=dp[i][j];
		//	cout<<dp[i+1][j]<<"   ";
		}
	//	cout<<endl;
	}
	cout<<dp[n][k];
	return 0;
}

Measured memory_bytes: 79104
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;
const int MAXN = 1e5+10 ; 
int n ; 
vector<int> graph[MAXN] ; 
map<pair<int,int> ,int> weight ; 
int vis[MAXN] ; 
int clr[MAXN] ; 
void dfs(int x,int color){
	if ( vis[x] ) return ; 
	vis[x] = true ; 
	if ( clr[x] == -1 ){
		clr[x] = color ; 
	}
	for(int c : graph[x]){
		if ( weight[{x,c}] % 2 == 0 ){
			clr[c] = clr[x] ; 
		}
		else clr[c] = !clr[x] ; 
		dfs(c,clr[c]);
	}
}
int main(){
	cin >> n ;     
	memset(clr,-1,sizeof clr);
	for(int i=0;i<n-1;i++){
		int x , y , w; 
		cin >> x >> y >> w ; 
		graph[x].push_back(y) ; 
		graph[y].push_back(x) ; 
		weight[{x,y}] = w ;
		weight[{y,x}] = w ;
	}
	for(int i=1;i<=n;i++){
		if ( !vis[i] ){
			dfs(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		cout << clr[i] << endl;
	}
    return 0 ;
}


Measured memory_bytes: 21888
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,a,ma=-50,mi=50;
  cin>>N>>a;
  vector<int> x(N);
  for(int &i:x){
    cin>>i;
    i-=a;
    ma=max(ma,i),mi=min(mi,i);
  }
  if(mi*ma>0){
    cout<<0<<endl;
    return 0;
  }
  mi*=N;
  ma*=N;
  vector<vector<int>> A(N+1,vector<int>(ma-mi+1));
  for(int i=0;i<=ma-mi;i++)
    A[0][i]=0;
  A[0][0-mi]=1;
  for(int j=1;j<=N;j++){
    for(int i=0;i<=ma-mi;i++){
      A[j][i]=A[j-1][i];
      if(ma-mi>=i-x[j-1] && i-x[j-1]>=0){
        A[j][i]+=A[j-1][i-x[j-1]];
      }
    }
  }
  cout<<A[N][0-mi]-1<<endl;
}

Measured memory_bytes: 4296
#include<iostream>
void print_array(int A[],int N){
      for(int j=0;j<N;j++){
      std::cout<<A[j];
      if(j!=N-1) std::cout<<' ';
    }
    std::cout<<'\n';
}
int main(){
  int N;
  std::cin>>N;
  int A[N];
  for(int i=0;i<N;i++){
    std::cin>>A[i];
  }
    print_array(A,N);
  for(int i=1;i<=N-1;i++){
    int v=A[i];
    int j=i-1;
    while(j>=0&&A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
    }
    print_array(A,N);
  }
  return 0;
}


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

int main() {
  int N;
  double r;
  cin >> N;
  if(N==1)
    r = 1.0000000000;
  else if(N%2==0)
    r = 0.5000000000;
  else
    r = ((N/2)+1.0)/N;
  cout << setprecision(8) << r << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10010
#define llg long long 
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,mid,ans,x;
int main()
{
	//yyj("A");
	cin>>x;
	llg l=1,r=1e9;
	while (l<=r)
	{
		mid=(l+r)>>1;
		if ((llg)mid*(mid+1)/2>=x) {r=mid-1,ans=mid;} else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
using LL = long long;
using PII = pair<int, int>;
#define F first
#define S second


const int maxn = 1e5 + 10;
int n;
LL a[maxn], b[maxn];

int main() {
  scanf("%d", &n);
  REPE(i, 1, n)
    scanf("%lld%lld", &a[i], &b[i]);
  LL ans = 0;
  for (int i = n; i >= 1; --i) {
    a[i] += ans;
    LL t = a[i] % b[i];
    if (t) ans += b[i] - t;
  }
  printf("%lld\n", ans);
  return 0;
}



Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << endl;
#else
	#define DBG(X)
	#define endl '\n'
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const ll mod = 1e9 + 7;
const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }

void solve()
{
	ll a, b;
	cin >> a >> b;

	ll cur = 1, answ = 0;

	while(cur < b)
	{
		cur += a - 1;
		++answ;
	}

	cout << answ << endl;
}

int main()
{
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <algorithm>
#include <string>

using namespace std;

int main(){
    int n,k;
    string card[10];
    while(cin>>n>>k,n){
        set<string> s;
        for(int i=0;i<n;++i) cin>>card[i];
        sort(card,card+n);
        do{
            string cb;
            for(int i=0;i<k;++i) cb +=card[i];
            s.insert(cb);
        }while(next_permutation(card,card+n));
        cout<<s.size()<<endl;
    }
    return 0;
}

Measured memory_bytes: 3372
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define INF 1000000007
using namespace std;

int main(void) {
	int n,count=0;cin >> n;
	vector<string> s(n);
	for(int i=0; i<n; i++){
		cin >> s[i];
	}
	string t;cin >> t;
	for(int i=0; i<n; i++){
		if(s[i]<=t)count++;
		for(int j=0; j<s[i].size(); j++){
			if(s[i][j]=='?')s[i][j]='z';
		}
	}
	int high=count+1;
	count=0;
	for(int i=0; i<n; i++){
		if(s[i]<t)count++;
	}
	cout << count+1;
	for(int i=count+2; i<=high; i++){
		cout << " " << i;
	}cout << endl;
	return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
struct TwoSat {
    int n, nmark = 0; vector<vector<int> > adj;
    vector<int> preorderof, stack;
    vector<bool> instack; vector<int> result;
    TwoSat(int nvar): n(2*nvar), adj(n), preorderof(n, -1), instack(n, false), result(nvar, -1){}
    void add_or(int a, int b) { // 2 * a for "a" is true, 2*a+1 for "a" is false
        adj[a^1].push_back(b);
        adj[b^1].push_back(a);
    }
    bool solve(){ // result has size nvar = n / 2, result[i] == 1 means "i" is true
        for(int u = 0; u < n; ++u)
            if(preorderof[u] == -1) dfs(u);
        for(int u = 0; u < n;  ++u)
            for(int v : adj[u])
                if(result[u/2] == 1-(u&1) && result[v/2] != 1-(v&1))
                    return false;
        return true;
    }
    int dfs(int v){
        int reach = preorderof[v] = nmark++;
        stack.push_back(v); instack[v] = true;
        for(int u : adj[v])
            if(preorderof[u] == -1) reach = min(reach, dfs(u));
            else if(instack[u]) reach = min(reach, preorderof[u]);
        if(reach == preorderof[v]){
            int u;
            do{
                u = stack.back(); stack.pop_back();
                instack[u] = false;
                if(result[u/2] == -1) result[u/2] = 1 - (u & 1);
            } while(u != v);
        }
        return reach;
    }
};
const int maxn = 10100;
int x[maxn], y[maxn], n;
int all[maxn * 2], wh[2][maxn];
bool check(int d){
	int len = 2 * n;
	vector<int> ids(2 * len);
	int cnt = 0;
	for(int i = 0; i < len; i++) ids[i + len] = cnt++;
	for(int i = len - 1; i > 0; i--) ids[i] = cnt++;
	TwoSat s(cnt);
	auto connect = [&](int l, int r, int p){
		for(l += len, r += len + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1){
				s.add_or(2 * ids[l] + 1, p);
				l++;
			}
			if(r & 1){
				r--;
				s.add_or(2 * ids[r] + 1, p);
			}
		}
	};
	int l = 0, r = 0;
	for(int i = 0; i < len; i++){
		while(l < i && all[i] - all[l] >= d) l++;
		while(r < len && all[r] - all[i] < d) r++;
		if(l < i){
			connect(l, i - 1, 2 * ids[i + len] + 1);
		}
		if(i < r - 1){
			connect(i + 1, r - 1, 2 * ids[i + len] + 1);
		}
	}
	for(int i = 0; i < n; i++){
		s.add_or(2 * ids[wh[0][i] + len] + 1, 2 * ids[wh[1][i] + len] + 1);
		s.add_or(2 * ids[wh[0][i] + len], 2 * ids[wh[1][i] + len]);
	}
	for(int i = len - 1; i > 0; i--){
		// -p ^ s
		s.add_or(2 * ids[i], 2 * ids[2 * i] + 1);
		s.add_or(2 * ids[i], 2 * ids[2 * i + 1] + 1);
	}
	return s.solve();
}
int main(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
	vector<pair<int, int> > vals;
	for(int i = 0; i < n; i++){
		vals.push_back({x[i], i});
		vals.push_back({y[i], i});
	}
	vector<int> stk(n, 0);
	sort(vals.begin(), vals.end());
	for(int i = 0; i < 2 * n; i++){
		all[i] = vals[i].first;
		wh[stk[vals[i].second]++][vals[i].second] = i;
	}
	int lo = 0, hi = 1000000001, ans = 0;
	while(lo <= hi){
		int mid = (lo + hi)>>1;
		if(check(mid)) ans = mid, lo = mid + 1;
		else hi = mid - 1;
	}
	cout << ans << endl;
	return 0;
}



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

int main(){
  int X;
  cin >> X;
  int M, m;
  M = X/100+1;
  m = X/105;
  int sum;
  for(int i=0; i<=M; i++){
    for(int j=0; j<=M-i; j++){
      for(int k=0; k<=M-i-j; k++){
        for(int l=0; l<=M-i-j-k; l++){
          for(int p=0; p<=M-i-j-k-l; p++){
            for(int q=0; q<=M-i-j-k-l-p; q++){
              sum = 100*i+101*j+102*k+103*l+104*p+105*q;
              if(sum==X){
                cout << 1 << endl;
                return 0;
              }
            }
          }
        }
      }
    }
  }
  cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  long long x,y;
  bool operator < (const P &a )const{
    //if(y!=a.y)
    return y>a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
int o[301];
int l[10];
int j[302];

long long x,y,z,mod=1000000007;
//string r;
char r[111];

P u[1];
queue<int> q;

//stack<int> s;
set<int> s;
map<int,int> p;
vector<P> v[200101];

bool as(P a,P b)
{
  if(a.x==b.x)
  return a.y<b.y;
  return a.x<b.x;
}

int f()
{
  printf("? ");
  for(int t=1;t<=a;t++)
    printf("%d ",j[t]);
  puts("");
  fflush(stdout);
  
  
  
  
  scanf("%s",r);
  if(r[0]=='R') return 1;
  return 0;
  
}

int main()
{
  scanf("%d",&a);
  iota(j+1,j+a+1,1);
  b=f();
  n=1,m=a;
  for(;n<m;)
  {
    int h=(n+m)/2+1;
    iota(j+1,j+a+1,h);
    c=f();
    if(c==b) n=h;
    else m=h-1;
  }
  memset(o,-1,sizeof(o));
  o[n]=b;
  o[n+a]=1-b;
  for(int t=1;t<=2*a;t++)
  if(o[t]<0)
  {
    if(t<n||t>n+a)
    {
      iota(j+1,j+a,n+1);
      j[a]=t;
      o[t]=f();
    }
    else
    {
      for(int t=1,w=1,h=a+n+1;t<=a;t++)
      {
        if(w<n) j[t]=w,w++;
        else j[t]=h,h++;
      }
      j[a]=t;
      o[t]=f();
    }
  }
  printf("! ");
  for(int t=1;t<=2*a;t++)
  if(o[t]==1) printf("R");
  else if(o[t]==0) printf("B");
  else printf("#");
  puts("");
  fflush(stdout);
}




Measured memory_bytes: 5460
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    double sum = 0;
    for(int i=1; i<=N; i++){
      int ans = i;
      int cnt = 0;
      while(ans<K){
        ans *= 2;
        cnt++;
      }
      sum += Math.pow(0.5, cnt)/N;
    }
    System.out.println(sum);
  }
}
                                    
    


Measured memory_bytes: 23764
INFTY=2000000000+1

class Node:
    def __init__(self,key=INFTY):
        self.key=key
        self.parent=-1
        self.left=-1
        self.right=-1

root=-1
T=[]
commands=[]
preorderList=[]
inorderList=[]

def readinput():
    global commands

    n=int(input())
    for _ in range(n):
        s=input().split()
        command=s[0]
        if(len(s)>1):
            op=s[1]
        commands.append((command,int(op)))

def insert(op):
    global T
    global root

    #print('[{}]'.format(op))
    zidx=len(T)
    z=Node(op)
    T.append(z)

    yidx=-1
    xidx=root
    while(xidx != -1):
        x=T[xidx]
        yidx=xidx
        if(z.key<x.key):
            xidx=x.left
            #print('left: {} < {}'.format(z.key, x.key))
        else:
            xidx=x.right
            #print('right')
    z.parent=yidx

    if yidx==-1:
        root=zidx
        #print('root changed')
    elif z.key<T[yidx].key:
        T[yidx].left=zidx
    else:
        T[yidx].right=zidx

def getPreorderList(id):
    global preorderList

    preorderList.append(id)
    node=T[id]
    if(node.left!=-1):
        getPreorderList(node.left)
    if(node.right!=-1):
        getPreorderList(node.right)

def getInorderList(id):
    global inorderList

    node=T[id]
    if(node.left!=-1):
        getInorderList(node.left)
    inorderList.append(id)
    if(node.right!=-1):
        getInorderList(node.right)

def printPreorderList():
    for i in preorderList:
        print(' '+str(T[i].key),end='')
    print('')

def printInorderList():
    for i in inorderList:
        print(' '+str(T[i].key),end='')
    print('')

def printT():
    global inorderList
    global preorderList

    inorderList=[]
    preorderList=[]
    
    getInorderList(root)
    printInorderList()
    getPreorderList(root)
    printPreorderList()
    #for node in T:
    #    print(node.key, node.parent, node.left, node.right)    

def main():
    global commands

    for command,op in commands:
        if(command=='insert'):
            insert(op)
        elif(command=='print'):
            printT()

if __name__=='__main__':
    readinput()
    main()


Measured memory_bytes: 196312
#include <bits/stdc++.h>
using namespace std;
int a[200001],b[200001];
double dou[200001];
int main()
{
    int d,n,cnt=0;
    cin>>n>>d;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];    
    }
    for(int i=0;i<n;i++){
        dou[i]=sqrt(a[i]*1.0*a[i]+b[i]*1.0*b[i]);
        if(dou[i]<=d)cnt++;
    }
    cout<<cnt;
    return 0;
}

Measured memory_bytes: 6704
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    print(0 if I()==1 else 1)
main()


Measured memory_bytes: 68384
N = gets.to_i
W = gets.split.map(&:to_i)

ans = Float::INFINITY

0.upto(N - 2) do |i|
  a = W[0..i].inject(:+)
  b = W[(i + 1)..-1].inject(:+)

  ans = [ans, (a - b).abs].min
end

puts ans


Measured memory_bytes: 1788
n,m,k=map(int,input().split())

def cmb(n, k, mod, fac, ifac):
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

fac,ifac=make_tables(998244353,n)



ans=0
for  i in range(k+1):
    #print(cmb(n-1,i,998244353,fac,ifac)*m*pow(m-1,n-1-i,998244353))
    ans+=cmb(n-1,i,998244353,fac,ifac)*m*pow(m-1,n-1-i,998244353)
    ans%=998244353

print(ans)


Measured memory_bytes: 32800
#include<stdio.h>

int main(void) {
	int a, b;
	scanf("%d %d", &a, &b);
	if (a > 12) {
		printf("%d", b);
	}
	else if (a > 5) {
		printf("%d", b / 2);
	}
	else
		puts("0");
	return 0;
}

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

bool func(){
  int N;
  cin >> N;
  int t, x, y, nx, ny;
  x = 0;
  y = 0;
  for(int i = 0 ; i < N ; i++){
    cin >> t >> nx >> ny;
    int count = abs(x - nx) + abs(y - ny);
    if(t < count)return false;
    if(count % 2){
      if(t % 2 == 0)return false;
    }
    else {
      if(t % 2 == 1)return false;
    }
  }
  return true;
}

int main(){
  cout << (func()? "Yes": "No") << endl;
  return 0;
}


Measured memory_bytes: 256
import numpy as np
D = int(input())
c = list(map(int, input().split()))
s = []
for i in range(D):
  tmp = list(map(int, input().split()))
  s.append(tmp)

for i in range(D):
  val_max = 0
  idx_max = 0
  for j in range(26):
    if val_max < s[i][j]:
      val_max = s[i][j]
      idx_max = j+1
  print(idx_max)

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

using namespace std;
int n,x,t;
int main()
{
    string n;
    cin>>n;
    long int sum=0;
    for(int i=0;i<n.length();++i)
    {
        sum+=(n[i]-48)%9;
        sum%=9;
    }
    if(sum==0)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
}


Measured memory_bytes: 3720
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
# ifdef __GNUC__
# if __cplusplus > 199711L
# include <unordered_set>
# include <unordered_map>
# else
# include <tr1/unordered_map>
# include <tr1/unordered_set>
using namespace tr1;
# endif
# else
# include <unordered_map>
# include <unordered_set>
# endif
using namespace std;

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
typedef unsigned char byte;
typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llong, llong> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-5; }

const int MAXN = 100100;
llong N;
llong vals[3][MAXN];
llong dp[2][MAXN];
llong sum[MAXN];

int main()
{
    while (cin >> N)
    {
        FO (i, N)
            cin >> vals[0][i];
        FO (i, N)
            cin >> vals[1][i];
        FO (i, N)
            cin >> vals[2][i];
        memset(dp, 0, sizeof(dp));
        sort(vals[0], vals[0] + N);
        sort(vals[1], vals[1] + N);
        sort(vals[2], vals[2] + N);
        for (int i = 0, j = 0; i < N; ++i)
        {
            while (j < N && vals[1][i] > vals[0][j])
                ++j;
            dp[0][i] = j;
        }
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < N; ++i)
        {
            sum[i] = ((i > 0) ? sum[i - 1] : 0) + dp[0][i];
        }
        for (int i = 0, j = 0; i < N; ++i)
        {
            while (j < N && vals[2][i] > vals[1][j])
                ++j;
            dp[1][i] = sum[j - 1];
        }
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < N; ++i)
        {
            sum[i] = ((i > 0) ? sum[i - 1] : 0) + dp[1][i];
        }
        cout << sum[N - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 5500
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long[] L = new long [100];
		L[0] = 2;
		L[1] = 1;
		
		for (int i = 2; i <= N; i++) {
			L[i] = L[i - 2] + L[i - 1];
		}
		
		System.out.println(L[N]);
	}
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define RREP(i,n) RFOR(i,0,n)

const int _N = 3e5 + 100;
int bitcount[] = {0,1,1,2,1,2,2,3};

int h,n;
bool b[4][10000];
int dp[2][1<<3];

int main(){
	cin >> h >> n;
	REP(i, n){
		int x,y;
		cin >> x >> y;
		b[x][y] = true;
	}
	REP(y, h-1){
		int *prev = dp[0];
		int *now = dp[1];
		REP(i, 1 << 3){
			now[i] = 0;
			REP(j, 1 << 3){
				bool flag = false;

				// check y height block
				REP(x, 3)REP(dx, 2)REP(dy, 2)
					if((i & (1 << x)) && b[x + dx][y + dy])
						flag = true;

				// check (y+1) height block
				if(y>=1)REP(x, 3)REP(dx, 2)REP(dy, 2)
					if((j & (1 << x)) && b[x + dx][y - 1 + dy])
						flag = true;

				// check hit i and j
				REP(x, 2)REP(dxi, 2)REP(dxj, 2)
					if((i & (1 << (x + dxi))) && (j & (1 << (x + dxj))))
						flag = true;

				// check in only i and in only j
				REP(x, 2)if((i & (1 << (x + 1))) && (i & (1 << x)))
					flag = true;
				REP(x, 2)if((j & (1 << x)) && (j & (1 << (x + 1))))
					flag = true;

				if(flag)continue;
				now[i] = max(now[i], prev[j] + bitcount[i]);
			}
		}
		swap(dp[0], dp[1]);
	}
	int ans = 0;
	REP(i, 1<<3)
		ans = max(ans, dp[0][i]);
	cout << ans << endl;
}

Measured memory_bytes: 3116
N,M = map(int,input().split())

nap = []

for i in range(N):
    A,B = map(int,input().split())
    list = [A,B]
    nap.append(list)

nap.sort()


cost = 0
for i in range(N):
    if M == 0:
        break
    for j in range(nap[i][1]):
        cost += nap[i][0]
        M -= 1
        if M == 0:
            break
    
    

print(cost)

Measured memory_bytes: 20064
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner; 

public class Main {
    private static Scanner sc;
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        int V = sc.nextInt();
        boolean E [][] = new boolean [V+1][V+1];
        
        for (int i=1; i<V+1; i++){
            int v = sc.nextInt();
            int k = sc.nextInt();
            for (int j=0; j<k; j++){
                int vk = sc.nextInt();
                E [v][vk] = true;
            }
        }
        Queue <Integer> Q = new ArrayDeque <Integer>();
        Q.add(1);
        
        int D [] = new int [V+1];
        D [1] = 1;
        
        while (Q.size()>0){
            int cur = Q.poll();
            for (int dst=1; dst<V+1; dst++){
                if (E[cur][dst] == true & D[dst] == 0){
                    D[dst]=D[cur]+1;
                    Q.add(dst);
                }           
            }           
        }
        for (int m=1; m<V+1; m++){
            System.out.println(m+" "+(D[m]-1));
        }
    }
}


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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)
#define mod 1000000007
typedef long long ll;

int main() {
    int n,T;
    cin>>n>>T;
    int m=1001;

    rep(i,n){
        int c,t;
        cin>>c>>t;
        if(t<=T&&c<m){
            m=c;
        }
    }

    if(m==1001){
        cout<<"TLE"<<endl;
        return 0;
    }

    cout<<m<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  int i=0, j, a, n, ans=0;
  cin >> n;
  a=n;
  for(; a>0; a/=10)
    i++;
  if(i%2) ans+=(n+1-pow(10,i-1));
    for(j=1; j<i;j+=2)
      ans+=9*pow(10, j-1);
  cout << ans << endl;
  return 0;
}


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

int main()
{
	int val[9];

	for (int i = 0; i < 3; i++) {
		cin >> val[i*3] >> val[i*3+1] >> val[i*3+2];
	}

//	for (int i = 0; i < 9; i++) {
//		cout << *(val+i) << "\n";
//	}

	if (
		*(val + 1) - (*(val + 2)) == *(val + 4) - (*(val + 5)) && 
		*(val + 4) - (*(val + 5)) == *(val + 7) - (*(val + 8)) &&
		*(val) - *(val + 3) == *(val + 1) - (*(val + 4)) &&
		*(val + 1) - (*(val + 4)) == *(val + 2) - (*(val + 5)) &&
		*(val)-(*(val + 1)) == *(val + 3) - (*(val + 4)) &&
		*(val + 3) - (*(val + 4)) == *(val + 6) - (*(val + 7)) &&
		*(val + 3) - (*(val + 6)) == *(val + 4) - (*(val + 7)) &&
		*(val + 4) - (*(val + 7)) == *(val + 5) - (*(val + 8))
		) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3624
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

vector<vector<ll>> table;
vector<vector<pair<ll,ll>>> memo;
string s,t;

ll dp(ll n,ll m){
  if(n<0||m<0) return 0;
  if(table.at(n).at(m)>-INF) return table.at(n).at(m);
  table.at(n).at(m)++;
  if(s.at(n)==t.at(m)){
    memo.at(n).at(m)={n-1,m-1};
    return table.at(n).at(m)=dp(n-1,m-1)+1;
  }
  if(chmax(table.at(n).at(m),dp(n-1,m))){
    memo.at(n).at(m)={n-1,m};
  }
  if(chmax(table.at(n).at(m),dp(n,m-1))){
    memo.at(n).at(m)={n,m-1};
  }
  return table.at(n).at(m);
}

  
int main() 
{
  cin>>s>>t;
  ll N=s.size(),M=t.size();
  table=vector<vector<ll>>(N,vector<ll>(M,-INF));
  memo=vector<vector<pair<ll,ll>>>(N,vector<pair<ll,ll>>(M,{0,0}));
  
  dp(N-1,M-1);
  
  string ans="";
  ll n=N-1,m=M-1;
  while(true){
    //cout<<n<<" "<<m<<endl;  
    if(n<0||m<0) break;
    if(s.at(n)==t.at(m)) ans+=s.at(n);
    if(dp(n,m)<=0) break;
    tie(n,m)=memo.at(n).at(m);
  }
  reverse(ans.begin(),ans.end());
  
  cout<<ans<<endl;
    
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}

#define deb(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define END '\n'
#define inf 9e18
#define ff first
#define ss second
#define pb push_back

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << ((b - a == c - b) ? "YES" : "NO");
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3568
#include<stdio.h>
int main()
{
	char pos='A',s,t;
	for(;;)
	{
		if(scanf("%c,%c\n",&s,&t)==EOF)
			break;
		if(pos==s)
			pos=t;
		else if(pos==t)
			pos=s;
	}
	printf("%c\n",pos);
	return 0;
}

Measured memory_bytes: 548
#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=2e5+5;
int n,k,a[MN];
ll Ans;
int main(){
	scanf("%d%d",&n,&k);
	for(reg int i=1;i<=n;i++)scanf("%d",a+i);
	sort(a+1,a+1+n);
	for(reg int i=1;i<=n-k;i++)Ans+=a[i];
	printf("%lld\n",Ans);
	return 0;
}

Measured memory_bytes: 1024