akhauriyash/Code-Regression huggingface dataset:
// Problem : B - Counting Roads
// Contest : AtCoder - AtCoder Beginner Contest 061
// URL : https://atcoder.jp/contests/abc061/tasks/abc061_b
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
int n,m;cin>>n>>m;
int arr[n+1]={0};
while(m--)
{
	int x,y;cin>>x>>y;
	arr[x]++;
	arr[y]++;
}
for(int i=1;i<=n;i++)
cout<<arr[i]<<"\n";
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


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

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

	int N, M;
	scanf("%d %d", &N, &M);

	//奇数
	if (N % 2 == 1) {
		for (int i = 0; i < M; i++) {
			cout << 1 + i << " " << N - i << "\n";
		}
	} else {
		for (int i = 0; i < ((N / 2 - 1) + 1) / 2; i++) {
			if (i >= M) {
				return 0;
			}
			cout << 1 + i << " " << N - i << "\n";
		}
		for (int i = ((N / 2 - 1) + 1) / 2; i < M; i++) {
			cout << 1 + i << " " << N - i - 1 << "\n";
		}
	}

	return 0;
}

Measured memory_bytes: 3720
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

struct Node{
    int pos;
    int rem;
    int mag;
    Node(int p, int r, int m):pos(p), rem(r), mag(m){}
};

int main(){
    const int DY[4] = {-1, 0, 1, 0};
    const int DX[4] = {0, 1, 0, -1};
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> field(H);
    REP(i, H)cin >> field[i];
    int start = 0;
    REP(y,H)REP(x,W)if(field[y][x]=='S'){
        start = y*W+x;
    }
    vector<int> used(H*W);
    vector<int> next;
    queue<pair<int, int> > que;
    que.push(make_pair(start, K));
    while(!que.empty()){
        pair<int, int> n = que.front();que.pop();
        int p = n.first;
        if(used[p])continue;
        used[p] = 1;
        next.push_back(p);
        if(n.second==0)continue;
        int cy = p / W;
        int cx = p % W;
        REP(i, 4){
            int ny = cy + DY[i];
            int nx = cx + DX[i];
            if(ny<0 || nx<0 || ny>=H || nx>=W)continue;
            if(field[ny][nx]=='#')continue;
            que.push(make_pair(ny*W+nx, n.second-1));
        }
    }
    REP(i, next.size()){
        que.push(make_pair(next[i], 0));
    }
    int res = -1;
    used.assign(H*W, -1);
    while(!que.empty()){
        pair<int, int> n = que.front();que.pop();
        int p = n.first;
        if(used[p]!=-1)continue;
        used[p] = n.second;
        int cy = p / W;
        int cx = p % W;
        if(cy==0 || cx==0 || cy==H-1 || cx==W-1){
            res = n.second;
            break;
        }
        REP(i, 4){
            int ny = cy + DY[i];
            int nx = cx + DX[i];
            if(ny<0 || nx<0 || ny>=H || nx>=W)continue;
            que.push(make_pair(ny*W+nx, n.second+1));
        }
    }
    res = res / K + (res % K > 0 ? 1 : 0) + 1;
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 13184
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main() {
	int N, W; cin>>N>>W;
	vector<int> w(N), v(N);
	for(int i = 0; i < N; i++) cin>>w[i]>>v[i];

	vector<map<int, int> > dp(N+1);
	dp[0][0] = 0;
	int ans = 0;
	for(int i = 0; i < N; i++) {
		for(map<int, int>::iterator it = dp[i].begin(); it != dp[i].end(); ++it) {
			int weight = it->first;
			int value = it->second;
			dp[i+1][weight] = max(dp[i+1][weight],value);
			ans = max(ans, dp[i+1][weight]);
			if(weight+w[i]<= W ){
				dp[i+1][weight+w[i]] = max(dp[i+1][weight+w[i]],value+v[i]);
				ans = max(ans, dp[i+1][weight+w[i]]);
			}
		}

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


Measured memory_bytes: 4864
#include <iostream>
#include <string>

int main()
{
    std::string S;
    std::cin >> S;
    
    if (S[S.size()-1] == 's')
    {
        std::cout<< S+"es" <<std::endl;
    }
    else{
        std::cout<< S+"s" <<std::endl;
    }

    return 0;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll k;
cin>>k;
if(k>1&&k<=50){
    vector<int> a(k,k);
    cout<<k<<endl;
    for(int i=0;i<k;i++)cout<<a[i]<<" ";
    cout<<endl;
}
else if((k==1||k==0)){
    if(k==0){
        cout<<2<<endl;
        cout<<1<<" "<<1<<endl;
    }
    else {
        cout<<2<<endl;
        cout<<0<<" "<<2<<endl;
    }
}
else{
    ll t=k%50;
    cout<<50<<endl;
    vector<ll> a(50,k/50+50);
    for(int i=t;i<50;i++)a[i]-=t+1;
    for(int i=0;i<50;i++)cout<<a[i]<<" ";
    cout<<endl;
    
}
}


Measured memory_bytes: 256
// 参考
// https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// Input macro
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r"3 4 5
" => r"6",

r"5 12 13
" => r"30",

r"45 28 53
" => r"630"
}

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        a: f32,
        b: f32,
        c: f32
    }

    let s = (a + b + c) / 2.0;

    (s * (s - a) * (s - b) * (s - c)).sqrt().to_string()
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(int i=0;i<(n);i++)
int inf = 1000000000;
ll INF = 1000000000000000000;
int n, a, b, c, q, k, x, y;
struct edge {ll to, cost;};
edge make_edge(ll a,ll b){
	edge x;
	x.to = a;
	x.cost = b;
	return x;
}
vector<edge> f[100010];
ll d[100010];
void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P>> que;
	fill(d, d + 100010, INF);
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		ll v = p.second;
		if (d[v] < p.first)continue;
		for (int i = 0; i < f[v].size(); i++) {
			edge e = f[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(make_pair(d[e.to], e.to));
			}
		}
	}
}
int main() {
	cin >> n;
	rep(i, n - 1) {
		cin >> a >> b >> c;
		f[a].push_back(make_edge(b, c));
		f[b].push_back(make_edge(a, c));
	}
	cin >> q >> k;
	dijkstra(k);
	rep(i,q){
		cin >> x >> y;
		cout << d[x] + d[y] << endl;
	}
	return 0;
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
int main() {
    int H,N; cin>>H>>N;
    vector<int> A(N);
    int tmp=0;
    for(int i=0;i<N;i++){
        cin>>A[i];
        tmp=tmp+A[i];
    }
    if(H<=tmp){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(){
  int a,b,c=0;

   scanf("%d%d%d",&a,&b,&c);

  while(a!=-1 || b!=-1 || c!=-1){

   if(a==-1||b==-1)
     printf("F\n");
   else if(a+b>=80)
     printf("A\n");
   else if(a+b>=65&&a+b<80) 
     printf("B\n");
   else if(a+b>=50&&a+b<65)
     printf("C\n");
   else if(a+b>=30&&a+b<50){
     if(c>=50)
       printf("C\n");
     else
       printf("D\n");
   }
   else 
     printf("F\n");
     scanf("%d%d%d",&a,&b,&c);
 }
  return 0;
}    

Measured memory_bytes: 584
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 705;
const int MAXM = 490005;

int n, m, cnt, a, b, color[MAXN];
bool Map[MAXN][MAXN], f[2][MAXN][MAXN];
queue<int> q;

namespace Graph{
	int ecnt, head[MAXN], nxt[MAXM<<1], to[MAXM<<1];
	inline void init(){
		ecnt = 0;
		memset( head, -1, sizeof head );
	}
	inline void adde( int u, int v ){
		to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
		to[++ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt;
	}
}

inline bool bfs( int s ){
	using namespace Graph;
	color[s] = 1; q.push(s);
	while( !q.empty() ){
		int u = q.front(); q.pop();
		if( color[u] == 1 ) ++a;
		else ++b;
		for( int i = head[u]; ~i; i = nxt[i] ){
			int v = to[i];
			if( color[v] == color[u] ) return 0;
			if( color[v] == 3 - color[u] ) continue;
			color[v] = 3 - color[u]; q.push(v);
		}
	}
	return 1;
}

int main(){
	scanf( "%d%d", &n, &m );
	Graph::init();
	for( int i = 1; i <= m; ++i ){
		int x, y; scanf( "%d%d", &x, &y );
		Map[x][y] = Map[y][x] = 1;
	}
	for( int i = 1; i <= n; ++i )
		for( int j = i + 1; j <= n; ++j )
			if( Map[i][j] == 0 )
				Graph::adde( i, j );
	f[0][0][0] = 1;
	for( int i = 1; i <= n; ++i ){
		if( color[i] ) continue;
		a = b = 0;
		if( !bfs(i) ) return puts( "-1" ), 0;
		for( int i = 0; i <= n; ++i )
			for( int j = 0; j <= n; ++j )
				f[1][i][j] = 0;
		for( int i = 0; i <= n; ++i )
			for( int j = 0; j <= n; ++j )
				if( f[0][i][j] )
					f[1][i+a][j+b] = f[1][i+b][j+a] = 1;
		for( int i = 0; i <= n; ++i )
			for( int j = 0; j <= n; ++j )
				f[0][i][j] = f[1][i][j];
	}
	int ans = INF;
	for( int i = 0; i <= n; ++i )
		for( int j = 0; j <= n; ++j )
			if( f[0][i][j] )
				ans = min( ans, i*(i-1)/2+j*(j-1)/2 );
	printf( "%d\n", ans );
	return 0;
}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
#define sz 200005
#define faster_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;

int main()
{
    faster_io;
    int a[5];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    cout<<a[0]+a[1]<<endl;
    return 0;
}




Measured memory_bytes: 256
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, k = f.read_int_list()
    x = f.read_int_list()

    ans = float('inf')

    for i in xrange(n-k+1):
        if x[i] * x[i+k-1] > 0:
            ans = min(ans, max(abs(x[i]), abs(x[i+k-1])))
        else:
            ans = min(ans, abs(x[i])+abs(x[i+k-1])+min(abs(x[i]),abs(x[i+k-1])))


    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


Measured memory_bytes: 12940
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INF = 999999999;
const int MOD = (int)1e9 + 7;
const int EPS = 1e-9;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int m;
  vector<int> vec;
  REP(i,3*n){
      cin >> m;
      vec.push_back(m);
  }
  SORT(vec);
  REV(vec);
  ll ans = 0;
  REP(i,3*n){
      if (i%2==1)ans+=vec[i];
      if (i==(2*n-1))break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2420
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")
#define charsize 100005 //10^5+5

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a= c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod_MOD1(ll n){n+= n<0?((-n)/MOD1+1)*MOD1:0; return n%=MOD1;}
ll mod_p(ll n ,ll p){n+= n<0?((-n)/p+1)*p:0; return n%=p;}
ll change_into_num(char s[] , ll len, ll p){ return !p ? 0 : POW(10,p-1)*(s[len-p]-'0') + change_into_num(s,len,p-1); }

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

int main(void){
    // char ;
    ll a,b;
    // ll ans=0;
    scanf("%lld%lld",&a,&b);
    // ll [n];
    // rep(i,0,n){
    //     scanf("%lld",&[i]);
    // }
    if(ABS(a-b)%2 ){
        printf("IMPOSSIBLE\n");
    }else{
        printf("%lld\n",(a+b)/2 );
    }
    
    // printf("%lld\n");
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); ++i)
#define repf(i, from, to) for (int i = (from); i < (to); ++i)
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

int main() {
  int a, b, c, x;

  cin >> a >> b >> c >> x;
  int count = 0;
  rep(ai, a + 1) {
    if(ai * 500 > x) {
      break;
    }

    rep(bi, b + 1) {
      if(ai * 500 + bi * 100 > x) {
        break;
      }

      rep(ci, c + 1) {
        int sum = ai * 500 + bi * 100+ ci * 50;
        if(sum > x) {
          break;
        }

        if(sum == x) {
          count++;
        }
      }
    }
  }

  cout << count << endl;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define pb push_back
#define F first
#define S second
#define ld long double
#define vi vector<ll>
const int INF = 1e9;
const int N = 100005;

vi dp(3);
void solve() {
	ll n; cin >> n;
	for (ll day = 0; day < n; day++) {
		vi dp1(3);
		vi a(3);
		for (ll i = 0; i < 3; i++) cin >> a[i];
		for (ll i = 0; i < 3; i++) {
			for (ll j = 0; j < 3; j++) {
				if (i != j) {
					dp1[j] = max(dp1[j], dp[i] + a[j]);
				}
			}
		}
		dp = dp1;
	}

	cout << max({dp[0], dp[1], dp[2]});
}

int main() {

	FASTIO;
/*
#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
*/
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define RFOR(i, start, end) for (long long i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

template <class T> T up(T a, T div) { return (a + div - 1) / div; }

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

    int N, H;
    cin >> N >> H;
    vector<pair<ll, ll>> x(N);
    ll mxa = 0;
    for (auto &&i : x) {
        cin >> i.first >> i.second;
        chmax(mxa, i.first);
    }

    sort(ALL(x),
         [](pair<ll, ll> a, pair<ll, ll> b) { return a.second > b.second; });
    ll sum = 0;
    ll ans = 0;
    int i  = 0;
    bool f = false;
    while (sum < H) {
        if (x[i].second <= mxa || f) {
            ans += up(H - sum, mxa);
            break;
        }
        sum += x[i++].second;
        ans++;
        if (i == N)
            f = true;
    }

    print(ans);

    return 0;
}

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

int v[1001],w[1001];
int W;
int n;
int dp[100+1][10000+1];

void solve(){
    cin>>n>>W;
    for(int i=0; i<n; i++){
        cin>>v[i]>>w[i];
    }
    for(int i=0; i<n; i++){
        for (int j=0; j<=W; j++){
            if(j<w[i]){
                dp[i+1][j]=dp[i][j];
            }
            else{
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[n][W]<<endl;
}

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


Measured memory_bytes: 7012
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
using ll = long long;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    vector<int> x(n), y(n), h(n);
    rep(i, n)
    {
        cin >> x[i] >> y[i] >> h[i];
    }
    rep(CX, 101) rep(CY, 101)
    {
        int H = -1;
        bool ok = true;
        //h[i] > 0
        rep(i, n)
        {
            if (h[i] > 0)
            {
                int tmpH = h[i] + abs(x[i] - CX) + abs(y[i] - CY);
                if (H == -1)
                    H = tmpH;
                if (H != tmpH)
                {
                    ok = false;
                    break;
                }
            }
        }
        if (!ok)
            continue;
        //h[i] = 0
        rep(i, n)
        {
            if (h[i] == 0)
            {
                int tmpH = h[i] + abs(x[i] - CX) + abs(y[i] - CY);
                if (H > tmpH)
                {
                    ok = false;
                    break;
                }
            }
        }
        if (!ok)
            continue;
        printf("%d %d %d\n", CX, CY, H);
        return 0;
    }
    return 0;
}

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

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const int inf = 1e9 + 7;
const int N = 1e6 + 5;

typedef long long ll;

string s, a = "AKIHABARA", b = "KIHBR", c;
char last;
int pos;

int main()
{
      cin >> s;

      for(int mask = 0; mask < (1 << 9); mask ++)
      {
            string now;
            int bits = __builtin_popcount(mask);
            if(a.size() == bits + s.size())
            {
                  int pos = 0;
                  for(int i = 0; i < a.size(); i ++)
                  {
                        int j = mask & (1 << i);
                        if(j) now += 'A';
                        else now += s[pos ++];
                  }
                  if(now == a)
                  {
                        cout << "YES" << endl;
                        return 0;
                  }
            }
      }

      cout << "NO" << endl;
}


Measured memory_bytes: 256
import sys, math
import bisect, heapq
import collections

sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

gets = lambda: input().rstrip()
getn = lambda: int(input())
getmul = lambda: (int(i) for i in input().split())
getlist = lambda: [int(i) for i in input().split()]

n, k = getmul()
snukes = [1 for _ in range(n + 1)]
for _ in range(k):
    d = getn()
    A = getlist()
    for snuke in A:
        snukes[snuke] = 0

print(sum(snukes) - 1)


Measured memory_bytes: 9480
/*
 
@author
_      _          _                 _      _
\\    // /\    | | \  |     |    /\ \\    //     
 \\  // /__\   | |_/  |_____|   /__\ \\  //
  \\// /    \  | | \  |     |  /    \ \\//
   \/ /      \ | |_/  |     | /      \ \/
@ Indian Institute of Technology Bhilai

With practice comes perfection,
with knowledge comes wisdom.
Incorporate wisdom in you, practice will harvest better results.
Always learn from others, your method is good but someone's even better.
Results take time, run for wisdom, for innovation, for getting better.
Points are mere objects, either you solve first or you solve better.
Seek for betterment, for quality, pace is important but cannot outstand
the quality you persist.
Times are bad just as now but it'll improve, this is my passion and I promise 
I won't let it go. I'll build myself again like a fighter gets back up after 
being thrown to the ground.
I'll learn. I bet that. I promise that.
*/
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rep1(i,n) for(ll i=1; i<=n; i++)
#define pb push_back
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define alla(arr,n) arr, arr+n
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define fsync ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll maxx =  1e9+7;

bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b){
    return a.fi>b.fi;
}

ll inline power(ll a, ll b, ll p){
    a %= p;
    ll ans = 1;
    while(b>0){
        if(b & 1)
            ans = (ans*a)%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return ans;
}

ll inv(ll n, ll p){
    return power(n,p-2, p);
}

bool inline isPrime(ll n) { 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
    return true; 
}

template<class T>
void printv(T &v, ll n){
    if(n==-1)
        n = v.size();
    rep(i,n)
        cout << v[i] << " ";
    cout << "\n";
}

void solve(){
    ll n,m,x,ans=maxx;
    cin>>n>>m>>x;
    vector<ll> c(n);
    ll arr[n][m];
    rep(i,n){
        cin>>c[i];
        rep(j,m)
            cin>>arr[i][j];
    }
    rep(i,1<<n){
        ll xx=i;
        vector<ll> t(m,0);
        ll d=0,cc=0;
        while(xx){
            if(1&xx){
                rep(e,m){
                    t[e]+=arr[d][e];
                }
                cc+=c[d];
            }
            d++;
            xx>>=1;
        }
        ll k=0;
        rep(e,m){
            if(t[e]>=x)
                k++;
        }
        if(k==m){
            ans = min(ans,cc);
        }
    }
    if(ans==maxx)
        cout << -1<<"\n";
    else
        cout << ans << "\n";

}

int main(){
    fsync
    ll test=1;
    // cin >> test;
    while(test--){
        solve();
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a) ? "POSSIBLE" : "IMPOSSIBLE")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
    int n,m;
    int ans=0;
    cin >>n>>m;
    int a,b;
    vector<vector<int>>path(n);
    rep(i,m){
        cin>>a>>b;
        a--;
        b--;

        path[a].push_back(b);
        path[b].push_back(a);
    }
    sort(all(path[0]));
    sort(all(path[n-1]));
    if(path[n-1].size()!=0){
    for(auto itr=path[0].begin();itr!=path[0].end();itr++){
        if(*lower_bound(all(path[n-1]),*itr)==*itr){
            ans=2;
        }
    }
    }
    cout<<solve(ans)<<endl;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  vll x(5);
  REP(i,5)cin>>x[i];

  REP(i,5){
    if(x[i]==0)
      cout<<i+1<<endl;
  }

}



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

int main()
{
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  int i, j;
  bool ok;
  for(i = 0; i < n; i++)
  {
    ok = true;
    for(j = i; j < n; j++)
    {
      if(s.at(j) != t.at(j-i))
      {
        ok = false;
        break;
      }
    }
    if(ok)break;
  }
  cout << n + i << endl;
}

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

int main() {
    int N, X; cin >> N >> X;
    vector<int> L(N);
    int sum = 0;
    for (int i = 0; i < L.size(); i++) {
        cin >> L.at(i);
        sum += L.at(i);
    }
    
    int count = N + 1, i = N - 1;
    while (sum > X) {
        sum -= L.at(i);
        count--;
        i--;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i=0; i<n; i++)
        cin >> a[i];

    vector<long long> sm(2*m+1, 0);
    vector<long long> sm2(2*m+1, 0);
    long long ans = 0;
    for(int i=0; i<n-1; i++){
        int s = a[i];
        int t = a[i+1];
        if(t < s) t += m;
        ans += t - s;
        if(t == s + 1) continue;
        sm[s+2]++;
        sm[t+1]--;
        sm2[t+1] -= t - (s+2) + 1;
    }

    for(int i=1; i<2*m+1; i++)
        sm[i] += sm[i-1];

    for(int i=0; i<2*m+1; i++) sm[i] += sm2[i];

    for(int i=1; i<2*m+1; i++)
        sm[i] += sm[i-1];

    for(int i=1; i<=m; i++) sm[i] += sm[i+m];
    long long tmp = 0;
    for(int i=1; i<=m; i++) tmp = max(tmp, sm[i]);

    cout << ans - tmp << endl;

    return 0;
}

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    long long a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    long long ma=a[0],mi=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]>ma)ma=a[i];
        if(a[i]<mi)mi=a[i];
    }
    cout<<ma-mi;
    return 0;
}


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

ll INF=1000000000000000;
ll mod=1000000007;

ll i,j,k;

int main(){
    ll n,a,b;cin>>n>>a>>b;
    vector<ll> h(n);
    for(i=0;i<n;i++){cin>>h[i];}


    ll ok=1000000001,ng=0;
    while(ok-ng>1){
        ll mid=(ng+ok)/2;
        ll sum=0;

        for(i=0;i<n;i++){
            if(h[i]-b*mid>0){//h[i]に基本攻撃mid*bを与えておく(mid:攻撃回数)
                if((h[i]-b*mid)%(a-b)==0){
                    sum+=(h[i]-b*mid)/(a-b);//sum:a-bの攻撃の回数    
                }else{
                    sum+=(h[i]-b*mid)/(a-b)+1;
                }
            }
        }

        if(sum<=mid){
            ok=mid;
        }else{
            ng=mid;
        }
    }

    cout<<ok<<endl;
    return 0;
}

Measured memory_bytes: 1024
N,M = map(int,input().split())
a = list()
b = list()
for i in range(M):
  tmp_a,tmp_b =  map(int, input().split())
  a.append(tmp_a)
  b.append(tmp_b)
print(min(b)-max(a)+1 if min(b)-max(a) >= 0 else 0)

Measured memory_bytes: 16744
S = input()
l = len(S)
s = list(S)
c = 0
s.append("U")

for i in range(-(-l//2)):
    d = 2*i
    if s[d] == "L":
        print("No")
        c = 1
        break
    if s[d+1] == "R":
        print("No")
        c = 1
        break
if c == 0:
    print("Yes")


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

int main() {
  int N, K, a=1, i=0, j=0;
  cin >> N >> K;
  
  for(j=0; j<N; j++){
    if(a<K){
      a*=2;
    }
    else{
      a+=K;
    }
  }
  cout << a << endl;
}

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

int m[10][10];
int ax[12]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};
int ay[12]={-1,0,1,0,-1,1,1,-1,-2,0,2,0};

void dfs(int x,int y,int size){
  m[x][y]+=1;
  if(size==1){
    for(int i=0;i<4;i++){
      if(x-ax[i]<0 || x-ax[i]>9 || y-ay[i]<0 || y-ay[i]>9) continue;
      m[x-ax[i]][y-ay[i]]+=1;
    }
  }else if(size==2){
    for(int i=0;i<8;i++){
      if(x-ax[i]<0 || x-ax[i]>9 || y-ay[i]<0 || y-ay[i]>9) continue;
      m[x-ax[i]][y-ay[i]]+=1;
    }
  }else if(size==3){
    for(int i=0;i<12;i++){
      if(x-ax[i]<0 || x-ax[i]>9 || y-ay[i]<0 || y-ay[i]>9) continue;
      m[x-ax[i]][y-ay[i]]+=1;
    }
  }

}


int main(){
  int x,y,size,clear=0,color=0;

  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      m[i][j]=0;
    }
  }

  while(scanf("%d,%d,%d",&x,&y,&size) != EOF){
    dfs(x,y,size);
  }

  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      if(m[i][j]==0){
	clear++;
      }else if(m[i][j]>color){
	color=m[i][j];
      }

    }
  }

  cout << clear << endl;
  cout << color << endl;

}

Measured memory_bytes: 1200
N, K = map(int, input().split())
H = [0] + list(map(int, input().split()))

DP = [0] * (N+1)

for i in range(2, N+1):
  k = max(i-K, 1)
  DP[i] = min(dp + abs(h - H[i]) for dp, h in zip(DP[k:i], H[k:i]))
print(DP[N])


Measured memory_bytes: 13980
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,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)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = 998244353;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<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);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


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

  Int N;
  cin>>N;
  vector<Int> D(N);
  cin>>D;
  Int ans = 1;
  if(D[0] != 0) ans = 0;

  sort(D.begin(), D.end());
  map<Int, Int> cnt;
  cnt[-1] = 1;

  for(Int i=0;i<N;i++){
    Int d = D[i];
    if(i != 0 && d == 0) ans = 0;
    ans *= cnt[d-1];
    ans %= mod;
    cnt[d]++;
    if(ans == 0) break;
  }

  cout<<ans<<endl;



  return 0;
}


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

AC = [0]*(n+1)
WA = [0]*(n+1)

for i in range(m):
    pi,si = input().split( )
    if si == "AC":
        AC[int(pi)] = 1
    elif not AC[int(pi)]:
        WA[int(pi)] += 1
print(sum(AC),end = " ")

ANS = [AC[i]*WA[i] for i in range(n+1)]
print(sum(ANS))

Measured memory_bytes: 51800
import numpy as np


def lagrange(DEG, MOD):
    DIV = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 5 * 4 * 3 * 2 * 1

    def sub(n):
        result = 0
        for j in range(5, n + 1):
            tmp = 1
            for i in range(9):
                tmp *= j + 4 - i
            for i in range(5):
                tmp *= 5 + (n - j) // 2 - i
            tmp //= DIV
            result += tmp
        return result

    def np_pow(arr, exp, mod):
        res = np.ones_like(arr)
        tmp = arr.copy()
        while exp:
            if exp & 1:
                res = res * tmp % mod
            tmp = tmp * tmp % mod
            exp >>= 1
        return res

    even_result = np.array([sub(2 * x) for x in range(1, DEG + 1)], dtype=np.int64) % MOD
    odd_result = np.array([sub(2 * x + 1) for x in range(1, DEG + 1)], dtype=np.int64) % MOD

    base_coef = np.zeros((DEG, DEG), dtype=np.int64)
    base_coef[:, -1] = 1
    indices = np.arange(1, DEG + 1, dtype=np.int64)
    invs = np.ones(DEG, dtype=np.int64)
    for i in range(1, DEG + 1):
        idx = indices != i
        base_coef[idx, :-1] += base_coef[idx, 1:] * -i
        base_coef %= MOD
        invs[idx] *= indices[idx] - i
    base_coef *= np_pow(invs % MOD, MOD - 2, MOD)[:, None]
    base_coef %= MOD

    even_coef = even_result[:, None] * base_coef % MOD
    odd_coef = odd_result[:, None] * base_coef % MOD
    even_coef = even_coef.sum(axis=0) % MOD
    odd_coef = odd_coef.sum(axis=0) % MOD

    return even_coef, odd_coef


DEG = 16
MOD = 10 ** 9 + 7
even_coef, odd_coef = lagrange(DEG, MOD)

t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        m = n // 2
        coef = even_coef
    else:
        m = (n - 1) // 2
        coef = odd_coef

    ms = np.ones(DEG, dtype=np.int64)
    for i in range(1, DEG):
        ms[i] = ms[i - 1] * m % MOD

    ans = (ms * coef % MOD).sum() % MOD
    buf.append(ans)

print('\n'.join(map(str, buf)))


Measured memory_bytes: 27116
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a;
  cin>>a;
  vector<int> b(a);
    for(int i=0;i<a;i++)
      cin>>b.at(i);
  sort(b.begin(),b.end());
  cout<<b.at(a/2)-b.at(a/2-1)<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin >> n;
   map<pii,int> cnt;
   f(i,1,n+1){
      string s = to_string(i);
      cnt[{s[0]-'0',s.back()-'0'}]++;
   }
   int ans = 0;
   f(i,1,n+1){
      string s = to_string(i);
      ans += cnt[{s.back()-'0',s[0]-'0'}];
   }
   cout << ans << '\n';
   return 0;
}

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<int> x(m);
	for (auto& e : x)
		cin >> e;
	// x.push_back(x.back());
	sort(x.begin(), x.end());
	vector<int> absum;
	for (int i = 0; i < m - 1; i++) {
		absum.push_back(abs(x[i + 1] - x[i]));
	}

	int ans = 0;
	sort(absum.begin(), absum.end());
	for (int i = 1; i < n; i++)
		if (!absum.empty()) absum.pop_back(); 
	for (int i = 0; i < absum.size(); i++) {
		ans += absum[i];
	}

	cout << max(0, ans) << endl;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll gi()
{
	char c=getchar(); ll x=0;
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
	return x;
}
const int N=1e5+5;
ll a[N],num[N],ans[N];
int t,n,m;
int main()
{
	n=gi(),t=gi();
	a[++m]=n;
	while(t--)
	{
		ll x=gi();
		for(;m&&a[m]>=x;--m);
		a[++m]=x; 
	}
	num[m]=1;
	for(int i=m-1;i;--i)
	{
		ll r=a[i+1]%a[i];
		while(r>a[1])
		{
			int p=upper_bound(a+1,a+1+m,r)-a-1;
			num[p]+=num[i+1]*(r/a[p]);
			r%=a[p];
		}
		ans[r]+=num[i+1];
		num[i]+=num[i+1]*(a[i+1]/a[i]);
	}
	ans[a[1]]+=num[1];
	for(int i=n;i;--i) ans[i]+=ans[i+1];
	for(int i=1;i<=n;++i) printf("%lld ",ans[i]);
}


Measured memory_bytes: 4096
// https://atcoder.jp/contests/abc129/tasks/abc129_c

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF (1e9)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// int gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// int lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll sum = 0;
    cin >> n;
    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    int avg = sum / 2;
    int ans = 0, ans2 = 0;
    for (auto x : w) {
        ans += x;
        if (ans > avg) {
            break;
        }
        ans2 = ans;
    }
    if (abs(avg - ans) < abs(avg - ans2)) {
        cout << abs(abs(sum - ans) - ans) << endl;
    } else {
        cout << abs(abs(sum - ans2) - ans2) << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define re register
using namespace std;
struct ios{
	template <typename ty> inline ios& operator >> (ty &x)
	{
		register int f=1;x=0;register char c=getchar();
		for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
		for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
		x*=f;return *this;
	}
	template <typename ty>  inline ios& operator << (ty x)
	{
		if(x<0) x=-x,putchar('-');
		if(x>9) *this << x/10;
		putchar(x%10+48);
		return *this;
	}
	inline ios& operator << (char c){putchar(c);return *this;}
}io;
ll n,a[1000],sum,k,fac[1000],tot,b[1000];
inline bool check(int x)//ÒÔxÎª×î´ógcd 
{
	for(int i=1;i<=n;i++) b[i] = a[i]%x;//¶ÔÓÚÃ¿¸öa[i]ÕÒµ½ËûµÄ¶ÔÓÚxµÄÄ£Êý£¬
	sort(b+1,b+1+n);
	int cnt = 0;
	int l=1,r=n;
	while(l<r)
	{
		int dis = x-b[r];
		if(b[l] >= dis) cnt += dis,b[l] -= dis,b[r] += dis;
		else 
		{
			cnt += b[l],b[r] += b[l],b[l] -= b[l];
		}
		if(b[r]==x) r--;
		if(b[l]==0) l++;
	}
	return cnt <= k;
}
 
int main()
{
	io >> n >> k;
	for(int i=1;i<=n;i++) io >> a[i],sum += a[i];
	ll ans = 1;
	tot = 0;
	for(ll i=1;i*i<=sum;i++)
	{
		if(sum%i==0) 
		{
			if(check(i)) ans = max(ans,i);
			if(check(sum/i)) ans = max(ans,sum/i);
		}
	}
//	sort(fac+1,fac+1+tot);
//	for(int i=tot;i>=1;i--)
//	{
//		if(check(fac[i])) 
//		{
////			io << fac[i];
//			ans = max(ans,fac[i]);
////			return 0;
//		}
//	}
	io << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const double PI=acos(-1);
 
int main(){
    ll h, n, a;
    cin >> h >> n;
    rep(i,n) {
        cin >> a;
        h -= a;
    }
 
    if (h <= 0) cout << "Yes" << endl;
    if (h  > 0) cout << "No" << endl;

    return 0;
    
}

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


 
int main() {
     int L;
     cin >> L;
     double V;
     if(L%3==0){
        V = L*L*L/27;
        printf("%0.12f",V);
        return 0;
     }
     if(L%3==1){
        int n;
        n = L/3;
        V = pow(n,3)+pow(n,2)+((double)n/(double)3)+((double)1/(double)27);
        printf("%0.12f",V);
        return 0;
     }
    if(L%3==2){
        int n;
        n = L/3;
        V = pow(n,3)+pow(n,2)*2+((double)4*(double)n/(double)3)+((double)8/(double)27);
        printf("%0.12f",V);
     }
     
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define pdump(p) cout<<" "<<#p<<"=("<<p.fst<<","<<p.snd<<")"
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std; using lint = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<lint, lint>;

int main(void) {
    int n, m;
    cin >> n >> m;
    
    struct city {
        int p;
        int y;
        int order;
        int rank;
    };
    
    vector<vector<city>> v(1e5 + 1);
    
    repeat (i, m) {
        city c;
        cin >> c.p >> c.y;
        c.order = i;
        v[c.p].push_back(c);
    }
    
    auto cmp_by_year = [](city a, city b) -> bool {
        return a.y < b.y;
    };
    
    auto cmp_by_order = [](city a, city b) -> bool {
        return a.order < b.order;
    };
    
    vector<city> w;
    repeat_from_to (i, 1, 1e5) {
        sort(v[i].begin(), v[i].end(), cmp_by_year);
        repeat (j, v[i].size()) {
            v[i][j].rank = j + 1;
            w.push_back(v[i][j]);
        }
    }
    
    sort(w.begin(), w.end(), cmp_by_order);
    
    for (city c: w) {
        cout << setfill('0') << right << std::setw(6) << c.p;
        cout << setfill('0') << right << std::setw(6) << c.rank;
        cout << endl;
    }
}

Measured memory_bytes: 8692
import Control.Applicative
import Control.Monad
import Data.List

main :: IO ()
main = do
    [a, b, x] <- fmap read . words <$> getLine :: IO [Int]
    let s = (a + x - 1) `div` x
    let t = b `div` x
    if s > t
        then print 0
        else print $ t - s + 1

Measured memory_bytes: 508
N, K = map(int, input().split())
MOD = 1_000_000_007
gcd_cnt = [0] * (K + 1)
for g in range(K, 0, -1):
    gcd_cnt[g] = pow(K // g, N, MOD)
    for g_mul in range(2, K // g + 1):
        gcd_cnt[g] -= gcd_cnt[g * g_mul]

ans = 0
for g, cnt in enumerate(gcd_cnt):
    ans += g * cnt % MOD
    ans %= MOD
print(ans)


Measured memory_bytes: 11240