akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        InputStreamScanner in = new InputStreamScanner(System.in);
        new Main().solve(in, out);
        out.flush();
    }

    private void solve(InputStreamScanner in, PrintWriter out) {
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        long k = in.nextLong();

        int x = k % 2 == 0 ? a - b : b - a;

        out.println(x);
    }

    static class InputStreamScanner {

        private InputStream in;

        private byte[] buf = new byte[1024];
        private int len = 0;
        private int off = 0;

        InputStreamScanner(InputStream in)	{
            this.in = in;
        }

        String next() {
            StringBuilder sb = new StringBuilder();
            for (int b = skip(); !isSpace(b);){
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char nextChar() {
            return (char)skip();
        }

        int skip() {
            for (int b; (b = read()) != -1;) {
                if (!isSpace(b)) {
                    return b;
                }
            }
            return -1;
        }

        private boolean isSpace(int c) {
            return c < 33 || c > 126;
        }

        private int read() {
            if (len == -1) {
                throw new InputMismatchException("End of Input");
            }
            if (off >= len){
                off = 0;
                try {
                    len = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException(e.getMessage());
                }
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[off++];
        }
    }
}

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

using namespace std;

const int NS = (int)1e5 + 4;
int N;
int arr[NS];
vector < pair < int, int > > ans;

int main(){
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i){
        scanf("%d", arr + i);
    }
    sort(arr + 1, arr + N + 1);
    for(int i = 2; i < N; ++i){
        if(arr[i] < 0){
            ans.push_back(make_pair(arr[N], arr[i]));
            arr[N] = arr[N] - arr[i];
        }
        else{
            ans.push_back(make_pair(arr[1], arr[i]));
            arr[1] = arr[1] - arr[i];
        }
    }
    printf("%d\n", arr[N] - arr[1]);
    for(auto&i:ans){
        printf("%d %d\n", i.first, i.second);
    }
    printf("%d %d\n", arr[N], arr[1]);
    return 0;
}


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


int main(){
	int n,k;
	cin >> n >> k;
	vector<int> H(n);
	ll sum = 0;
	rep(i,n) {
		cin >> H[i];
		sum += H[i];
	}
	sort(H.begin(), H.end());
	if(n>k){
		rep(i,k){
			sum -= H[n-1-i];
		}
		cout << sum << endl;
	}else{
		cout << 0 << endl;
	}
	return 0;
}


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

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

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

#define INF 1000000000

bool solve(int sq, int h){
  for(int nh=h+1; 2*nh*nh<sq; nh++){
    int nw=nh+1;
    while(nh*nh+nw*nw<sq) nw++;
    if(nh*nh+nw*nw==sq){
      cout << nh << " " << nw << endl;
      return true;
    }
  }
  return false;
}

int main(){
  int h,w;
  while(scanf("%d %d",&h, &w), h|w){
    int sq = h*h + w*w;

    while(!solve(sq, h)){
      sq++; h=0;
    }

  }
}

Measured memory_bytes: 1208
from __future__ import print_function
import numpy as np
import sys
import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy,functools
# from itertools import accumulate
# from collections import deque
import random

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

n = int(input())
l = np.array(list(map(int, input().split())))

# eprint(2*l.max())
# eprint(l.sum())
if 2*l.max()<l.sum():
    print("Yes")
else:
    print("No")


Measured memory_bytes: 14424
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

struct LCA {
    vector<vector<int>> par;
    vector<int> d;
    int n;
    LCA(vector<vector<int>> graph, int root) {
        n = graph.size();
        par.resize(n, vector<int>(30));
        d.resize(n, 0);
        function<void(int, int, int)> dfs = [&](int c, int p, int depth) {
            d[c] = depth;
            par[c][0] = p;
            for (auto ch : graph[c]) {
                if (ch != p) dfs(ch, c, depth + 1);
            }
        };
        dfs(0, 0, 0);
        for (int j = 1; j < 30; j++) {
            REP(i, n) { par[i][j] = par[par[i][j - 1]][j - 1]; }
        }
    }
    int getdistance(int u, int v) { return (d[u] + d[v]) - 2 * (d[query(u, v)]); }
    int query(int u, int v) {
        if (d[u] > d[v]) {
            swap(u, v);
        }
        for (int i = 29; 0 <= i; i--) {
            if (d[u] <= d[par[v][i]]) {
                v = par[v][i];
            }
        }
        /* LCA */
        for (int i = 29; 0 <= i; i--) {
            if (par[v][i] != par[u][i]) {
                v = par[v][i];
                u = par[u][i];
            }
        }
        if (u == v) {
            return u;
        } else {
            return par[v][0];
        }
    }
};

struct UnionFind {
    vector<int> parent, size;
    UnionFind(int n) {
        parent.resize(n, -1);
        size.resize(n, 1);
    }
    void unite(int x, int y) {
        if (same(x, y)) {
            return;
        }
        x = root(x);
        y = root(y);
        if (size[x] <= size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
    }
    bool same(int x, int y) { return (root(x) == root(y)); }
    int root(int x) {
        while (parent[x] != -1) {
            x = parent[x];
        }
        return x;
    }
    int getsize(int x) { return size[root(x)]; }
};
int n, m;
vector<vector<int>> graph;
void aoj(vector<int> bs) {
    REP(i, bs.size() - 1) { cout << bs[i] << " "; }
    cout << bs[bs.size() - 1] << endl;
}

signed main() {
    int n;
    cin >> n;
    vector<int> as(n);
    REP(i, n) { as[i] = i + 1; }
    aoj(as);
    while (next_permutation(as.begin(), as.end())) {
        aoj(as);
    }
}


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

int main(){
        int n,m,i,t1,t2,cnt=0,flg=0;
        cin >> n >> m;
        vector<vector<int>> r(n);
        vector<int> idx(n);
        for(i=0;i<n;++i){
                idx.at(i) = i;
        }
        for(i=0;i<m;++i){
                cin >> t1 >> t2;
                --t1; --t2;
                r.at(t1).push_back(t2);
                r.at(t2).push_back(t1);
        }
        do{
                if(idx.at(0)!=0) continue;
                else{
                        for(i=0;i<n-1;++i){
                                if(find(r.at(idx.at(i)).begin(), r.at(idx.at(i)).end(), idx.at(i+1))==r.at(idx.at(i)).end()){
                                        flg = 1;
                                        break;
                                }
                        }
                        if(flg==0) ++cnt;
                        flg = 0;
                }
        }while(next_permutation(idx.begin(), idx.end()));
        cout << cnt << endl;
        return 0;
}

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

using namespace std;
const int N=2e5+5;
int L[N],R[N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,k,c;
    cin>>n>>k>>c;
    string s;cin>>s;
    int idx=0,cur=-1;
    for(int i=0;i<(int)s.size();i++)
    {
        if(s[i]=='x') continue;
        if(cur==-1||i-cur>c)
            cur=L[idx++]=i;
    }
    if(idx!=k) return 0;
    idx=k-1;
    cur=-1;
    for(int i=(int)s.size()-1;i>=0;i--)
    {
        if(s[i]=='x') continue;
        if(cur==-1||cur-i>c)
            cur=R[idx--]=i;
    }
    for(int i=0;i<k;i++)
        if(L[i]==R[i])
            cout<<L[i]+1<<'\n';
    return 0;
}


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

int main() {
  double l;
  cin >> l;

  double ans = l * l * l / 27;

  printf("%.12f", ans);
  return 0;
}

Measured memory_bytes: 256
// @skylag
//I am into me now ;)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define SKY ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long int
int power(int a,int n,int m)
{
    int res=1;
    while(n)
    {
        if(n&1)
        {
            res=((res)*(a));
            n--;
        }
        else
        {
            a=((a)*(a));
            n/=2;
        }
    }
    return res;
}

void solve(int t)
{
    
    int x;
    cin>>x;
    if(x>=400 and x<=599)
        cout<<8;
    else if(x>=600 and x<=799)
        cout<<7;
    else if(x>=800 and x<=999)
        cout<<6;
    else if(x>=1000 and x<=1199)
        cout<<5;
    else if(x>=1200 and x<=1399)
        cout<<4<<"\n";
    else if(x>=1400 and x<1600)
        cout<<3;
    else if(x>=1600 and x<1800)
        cout<<2;
    else if(x>=1800 and x<2000)
        cout<<1;

}
int32_t main()
{
    SKY;
    //freopen("/Users/skylags/Desktop/input.txt","r",stdin);
    //freopen("/Users/skylags/Desktop/output.txt","w",stdout);
    int t=1;
    //cin>>t;
    int flag=1;
    while(t--)
    {
        solve(flag);
        flag++;
    }
}
/*Codechef July Lunchtime (Div.2)*/
//cout<<"Case #"<<t<<":"<<"\n";
//int n;
//cin>>n;
//vector<pair<int,int>> v(n);
//for(int i=0;i<n;i++)
//{
//    cin>>v[i].F>>v[i].S;
//}
//int ans=0;
//int temp=0;
//sort(ALL(v));
//int start=0;
//unordered_map<int,int> forward,backward;
//for(int i=0;i<n;i++)
//{
//
//}
//while(1)
//{
//    int temp=0;
//    for(int i=start;i<n;i++)
//    {
//        temp+=v[i].S;
//
//    }
//}
//ans=max(ans,v[n-1].S);
//cout<<ans<<"\n";


Measured memory_bytes: 3652
#include <cstdio>
#include <map>
using namespace std;

const int T = 1000;

int main() 
{
	int x;
	scanf("%d", &x);
	for (int i = 0; i <= T; ++i) for (int j = -T; j <= i; ++j) if ((long long)i * i * i * i * i - (long long)j * j * j * j * j == x) {
		printf("%d %d\n", i, j);
		return 0;
	}
	return 0;
}


Measured memory_bytes: 1728
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <set>
#include <cmath>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<n+1;i++)

struct Union_Find
{
    int *parent;
    int *rank;
    Union_Find(int N){
        parent = new int[N];
        rank = new int[N];
        for(int i=0;i<N;i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    void clear(){
        delete[] parent;
        delete[] rank;
    }

    int root(int x){
        // xの所属する集合のルートを返す.
        int p = parent[x];
        if(p==x) return x;
        else{
            int ans = root(p);
            parent[x] = ans;
            return ans;
        }
    }

    bool is_same(int x,int y){
        return root(x) == root(y);
    }

    void unite(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return;
        if(rank[x]<rank[y]) parent[x] = y;
        else{
            parent[y] = x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }
};

int main(){
    int N,M,K,a,b,c,d;
    vector<int> block[100000];
    int friends[100000];
    map<int,vector<int>> hoge;
    cin>>N>>M>>K;
    Union_Find T(N);
    rep(i,M){
        cin>>a>>b;
        a--;b--;
        T.unite(a,b);
        friends[a]++;
        friends[b]++;
    }
    int ans[100000];
    rep(i,N) hoge[T.root(i)].push_back(i);
    rep(i,N) ans[i] = hoge[T.root(i)].size();
    rep(i,K){
        cin>>c>>d;
        c--;d--;
        block[c].push_back(d);
        block[d].push_back(c);
    }
    rep(i,N){
        ans[i] --;
        ans[i] -= friends[i];
        rep(j,block[i].size()){
            if(T.is_same(block[i][j],i)) ans[i]--;
        }
        cout<<ans[i]<<" ";
    }cout<<endl;
    T.clear();
    return 0;
}

Measured memory_bytes: 16640
import java.io.BufferedReader

fun main() {
    val br = System.`in`.bufferedReader()
    val x = br.readInt()
    if(x >= 30){
        print("Yes")
    } else {
        print("No")
    }
}

private const val SPACE_INT = ' '.toInt()
private const val ZERO_INT = '0'.toInt()
private const val NL_INT = '\n'.toInt()

private fun BufferedReader.readInt(): Int {
    var ret = read()
    while (ret <= SPACE_INT) {
        ret = read()
    }
    val neg = ret == '-'.toInt()
    if (neg) {
        ret = read()
    }
    ret -= ZERO_INT
    var read = read()
    while (read >= ZERO_INT) {
        ret *= 10
        ret += read - ZERO_INT
        read = read()
    }

    while (read <= SPACE_INT && read != -1 && read != NL_INT) {
        mark(1)
        read = read()
    }
    if (read > SPACE_INT) {
        reset()
    }
    return if (neg) -ret else ret
}

Measured memory_bytes: 34256
n = int(input())
a = [int(x) for x in input().split()]
result = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j +1 , n):
            if a[i] != a[j] and a[i] != a[k] and a[j] != a[k]:
                if a[i] + a[j] > a[k] and a[i] + a[k] > a[j] and a[j] + a[k] > a[i]:
                    result += 1
print(result)

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

struct UnionFind{
    vector<int> parent;
    vector<int> size;
    vector<int> rank;

    /* constructor (initialize) */
    UnionFind(int n){
        parent.resize(n);
        size.resize(n);
        rank.resize(n);
        for(int i=0; i<n; i++){
            parent[i] = i;// completely-disjoint
            size[i] = 1;
            rank[i] = 0;// union by rank
        }
    }

    int root(int x){
        // terminal case
        if(parent[x] == x){
            return x;// by definition
        }

        // recursion
        parent[x] = root(parent[x]);// path compression : keep tree as shallow as possible
        return parent[x];
    }

    void merge(int x, int y){
        int rx = root(x);
        int ry = root(y);

        // if (root(x) == root(y)) do nothing;
        if (rx != ry){
            if(rank[rx] < rank[ry]){
                parent[rx] = ry;// root of merged tree = ry
                size[ry] += size[rx];
            }
            else if(rank[rx] == rank[ry]){
                parent[rx] = ry;
                size[ry] += size[rx];
                rank[ry] += 1;
            }
            else if(rank[rx] > rank[ry]){
                parent[ry] = rx;// root of merged tree = rx
                size[rx] += size[ry];
            }
        }
        return;
    }

    bool is_same(int x, int y){
        return root(x) == root(y);
    }

    int nodes(int x){
        return size[root(x)];
    }
};

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

    vector<int> a(m), b(m);
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i];
        a[i] -= 1;
        b[i] -= 1;
    }

    long long int count = n * (n-1) / 2;// number of pairs (a,b) = nC2
    vector<long long int> ans(m);
    
    UnionFind uf(n);
    for(int i=m-1; i>=0; i--){
        ans[i] = count;

        if(uf.is_same(a[i],b[i]) == false){
            count -= uf.nodes(a[i]) * uf.nodes(b[i]);
            uf.merge(a[i], b[i]);
        }
    }
    
    for(int i=0; i<m; i++){
        cout << ans[i] << endl;
    }
    return 0;
}

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

def cmb(n,r):
    if r > n:
        return 0
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    return cmb(n-1,r) + cmb(n-1,r-1)

ret = cmb(N,2) + cmb(M,2)
print(ret)

Measured memory_bytes: 3060
#define M'   '
char*s,T[M],*r=T;U[M*35];n;k;main(i){for(;gets(r+1);k=!--n)for(;*++r&=31;)U[r-T]=k|=!!n<<*r;for(;~i--;)for(s=r;s-->T;k=U[k]=U[k-=~-~*s*M]?:*s?s-T:0)n+=__builtin_popcount(U[s-T]&(U[k+M]^=!s[-1]<<*s));printf("%d",n+1);}

Measured memory_bytes: 135060
import math

A,B,H,M = map(int,input().split())
h = 0.5*(H*60+M)
m = 6*M
t = abs(h-m)
if t > 180:
    t = 360 - t

if t <= 90:
    p = math.cos(math.radians(t))*B - A
    q = math.sin(math.radians(t))*B
    print((p**2+q**2)**0.5)
else:
    p = math.cos(math.radians(180-t))*B+A
    q = math.sin(math.radians(180-t))*B
    print((p**2+q**2)**0.5)

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

int main(){
  int W, a, b;
  cin >> W >> a >> b;
  if(b<=a+W && b>=a || a<=b+W && a>=b) cout << 0 << endl;
  else cout << min(abs(b-a-W), abs(b+W-a)) << endl;
}

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

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

  int l_max, r_min;
  l_max = -1;
  r_min = 10000000;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    if (l > l_max) {
      l_max = l;
    }
    if (r < r_min) {
      r_min = r;
    }
  }

  if (r_min < l_max) {
    cout << 0 << "\n";
  } else {
    cout << r_min - l_max + 1<< "\n";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
ll n,a,b;
vector<ll> h;
bool die(ll x){
    ll count=0;
    REP(i,n){
        ll life = h[i] - x*b;
        if(life>0){
            count+=(life+a-b-1)/(a-b);
        }
    }
    if(count<=x){
        return true;
    }else{
        return false;
    }
}
ll bin_search(ll start, ll end){
    if(start+1==end) return end;
    if(die((start+end)/2)){
        return bin_search(start,(start+end)/2);
    }else{
        return bin_search((start+end)/2,end);
    }
}

int main(){
     cin >> n >> a >> b;
    REP(i,n){
        ll hh;
        cin >> hh; h.push_back(hh);
    }
    sort(h.begin(), h.end(), greater<ll>());
    ll ans = bin_search(0,1000000000);
    cout << ans << endl;

}

Measured memory_bytes: 1400
#include<stdio.h>
#include<math.h>

int main(){
  int i, n, point[1000];
  double heikin, bunsan;
  
  while(1){
    scanf("%d",&n);
    if(n==0) break;

    heikin=bunsan=0;

    for(i=0;i<n;i++){
      scanf("%d",&point[i]);
      heikin+=point[i];
    }
    heikin/=(double)n;

    for(i=0;i<n;i++) bunsan+=pow(point[i]-heikin,2);
    bunsan/=(double)n;

    printf("%f\n",sqrt(bunsan));
  }
  return 0;
}



Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
int main(){
    int h,w,n;
    cin>>h>>w>>n;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    int c=0;
    int x[h][w];
    for(int i=0;i<h;i++){
        if(i%2==0){
            for(int j=0;j<w;j++){
                x[i][j]=c+1;
                a[c]--;
                if(a[c]==0)c++;
            }
        }
        else {
            for(int j=w-1;j>=0;j--){
                x[i][j]=c+1;
                a[c]--;
                if(a[c]==0)c++;
            }
        }
    }
    for(int i=0;i<h;i++)for(int j=0;j<w;j++)cout<<x[i][j]<<endl;
    return 0;
}

Measured memory_bytes: 384
// Problem : D - Leaping Tak
// Contest : AtCoder - AtCoder Beginner Contest 179
// URL : https://atcoder.jp/contests/abc179/tasks/abc179_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// $%U%$
// Mere bas ka nahi hai
// still i'm trying
// apna time aayega
//
//        .--------------.  
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |  
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'                          		  
//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x,ll y,ll m){if(y==0)return 1;ll p=power(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
ll nCr(ll n,ll r,ll m){if(r>n)return 0;ll a=1,b=1,i;for(i=0;i<r;i++){a=(a*n)%m;--n;}while(r){b=(b*r)%m;--r;}return (a*power(b,m-2,m))%m;}
#define Test int t;cin>>t;while(t--)
#define endl '\n'
const ll mod=998244353;
void solve()
{
	ll n,k;
	cin >> n >> k;
	vector<array<ll,2>> v(k);
	for(int i=0;i<k;++i)
	cin >> v[i][0] >> v[i][1];
	vector<ll> dp(n+5),dp2(n+5);
	dp[1]=1;
	for(ll i=1;i<=n;++i)
	{
		dp2[i]+=dp2[i-1];
		dp2[i]%=mod;
		dp[i]+=dp2[i];
		dp[i]%=mod;
		for(int j=0;j<k;++j)
		{
			ll l=v[j][0];
			ll r=v[j][1];
			if(i+l<=n)
			{
				dp2[i+l]+=dp[i];
				dp2[i+l]%=mod;
			}
			if(i+r+1<=n)
			{
				dp2[i+r+1]-=dp[i];
				dp2[i+r+1]+=mod;
				dp2[i+r+1]%=mod;
			}
		}
	}
	cout << dp[n] << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//Test
	solve();
	return 0;
}


Measured memory_bytes: 6364
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <complex>
using namespace std;

typedef complex<int> Point;

int m;
Point line_ori[10];
Point lines[50][10];
Point lines2[50][10];

void normalize(Point *line) {
  Point p = line[0];
  for(int i = 0;i < m;i++) line[i] -= p;
  int ct = 0;
  for(int i = 0;i < 3;i++) {
    if(line[1].real() > 0) break;
    line[1] *= Point(0,-1);
    ct++;
  }
  for(int i = 2;i < m;i++) {
    for(int j = 0;j < ct;j++) line[i] *= Point(0,-1);
  }
}

int main() {

	int n;
	while(cin >> n && n != 0) {
	  int x,y,m2;
		cin >> m;
		for(int i = 0;i < m;i++) {
			cin >> x >> y;
			line_ori[i] = Point(x,y);
		}
		normalize(line_ori);
		m2 = m;

		for(int i = 0;i < n;i++) {
			cin >> m;
			for(int j = 0;j < m;j++) {
				cin >> x >> y;
				lines[i][j] = Point(x,y);
				lines2[i][m - j - 1] = Point(x,y);
			}

			if(m != m2) continue;
			
		        normalize(lines[i]);
			normalize(lines2[i]);

			bool f1 = true,f2 = true;
			for(int j = 0;j < m;j++) {
				f1 = f1 && (lines[i][j] == line_ori[j]);
				f2 = f2 && (lines2[i][j] == line_ori[j]);
			}
		      
			if(f1 || f2) cout << i + 1 << endl;
		} 
		cout << "+++++" << endl;

	}

}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define all(ppp) ppp.begin(),ppp.end()
#define out(ppp) cout<<(ppp)<<endl
#define out1(ppp) cout<<(ppp) 

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define pb push_back

typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<vpi> vvpi;

typedef set<pi> spi;

int WA[105000]={0};
bool AC[105000]={false};

const int INF=INT_MAX;




int main(){
       int N,M;
       cin>>N>>M;
       vi vt(N+1,0);
        int WAnum=0;
        int ACnum=0;
       for(int i=0;i<M;i++){
           int a;
           string s;
           cin>>a>>s;
           if(AC[a]){
               continue;
           }
           if(s=="AC"){
               AC[a]=true;
               ACnum++;
               WAnum+=WA[a];
           }else if(s=="WA"){
               WA[a]++;
           }
       } 

        cout<<ACnum<<" "<<WAnum<<endl;
    return 0;
}


Measured memory_bytes: 1152
N, M = map(int, input().split())
A = list(map(int, input().split()))
sum = sum(A)
cnt = 0
for i in range(N):
    if A[i] < sum*(1/(4*M)):
        cnt += 1
if (len(A) - cnt) >= M:
    print("Yes")
else:
    print("No")


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

#define rep(i, n) for (int i = 0; i < n; i++) 
#define rrep(i, n) for(int i = n-1; i>=0; i--)
#define range(i, n, m) for (int i = n; i < m; i++) 
#define rrange(i, n, m) for (int i = n - 1; i => m; i--) 

typedef long long int ll;
typedef unsigned long long int ull;


using namespace std;

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

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

	ll N, M;

	cin >> N >> M;

	if (M <= N) {
		cout << dec << 0;
		return 0;
	}

	vector<ll> X(M);
	rep(i, M) {
		cin >> X[i];
	}

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

	vector<ll> diff(M);
	rep(i, M - 1) {
		diff[i] = X[i + 1] - X[i];
	}

	sort(diff.begin(), diff.end(), greater<ll>());

	ll aa = 0;
	rep(i, N - 1) {
		aa += diff[i];
	}

	cout << dec << (X[M - 1] - X[0]) - aa;





	

	return 0;
}


Measured memory_bytes: 1792
program main
	implicit none
	integer :: n,l(1000),r(1000),sv
	integer::i
	read(*,*)n
	do i=1,n
		read(*,*)l(i),r(i)
	enddo
	do i=1,n
		sv=sv+r(i)-l(i)+1
	enddo
	write(*,*)sv
end program main


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

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

    int n,d;
    cin>>n>>d;
    long ans=0;
    while(n--)
    {
        double x,y;
        cin>>x>>y;
        if(sqrt(x*x + y*y)<=(double)d)
            ++ans;
    }
    cout<<ans<<"\n";
    return 0;
}



Measured memory_bytes: 3824
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
num = 0
tem = 1
ans = [0]*n
for i in a:
  if i != tem:
    ans[tem-1] = num
    tem = i
    num = 1
  else:
    num += 1
for i in ans:
  print(i)

Measured memory_bytes: 32244
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	long long int n = s.size();
	long long int count = 1;
	long long int i2;
	if(n == 2){
		if(s[0] == s[1]){
			cout << 1 << endl;
			return 0;
		}else{
			cout << 2 << endl;
			return 0;
		}
	}
	if(n == 1){
		cout << 1 << endl;
		return 0;
	}
	for(int i = 1;i < n - 2;i++){
		if(s[i] != s[i - 1]){
			count++;
		}else{
			count++;
			i += 2;
			if(i < n - 2){
				count++;
			}else if(i == n - 2){
				count++;
				if(s[n - 2] != s[n - 1]) count++;
				cout << count << endl;
				return 0;
			}else{
				count++;
				cout << count << endl;
				return 0;
			}
		}
		i2 = i;
	}
	if(s[n - 3] != s[n - 2] && s[n - 2] != s[n - 1]){
		count += 2;
	}else{
		count += 1;
	}
	cout << count << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll N;
  cin >> N;
  vector<ll> C(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> C.at(i);
  }
  sort(C.begin(), C.end());

  if (N == 1)
    FINALANS(2 * C.front() % MOD);

  ll p = 1;
  for (ll i = 0; i < N - 2; i++)
  {
    p *= 2;
    p %= MOD;
  }

  ll ans = 0;
  for (ll i = 0; i < N; i++)
  {
    ll tmp = C.at(i) * (p * (N + 1 - i) % MOD) % MOD;

    ans += tmp;
    ans %= MOD;
  }

  ans *= p * 4 % MOD;
  ans %= MOD;

  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9


bool num[51];
int N;
bool P;
ll dp[2][51]; // dp[i][j] : j以下の袋から、余りがiとなるような組み合わせの数 

void input() {
	cin >> N >> P;
	for (int i = 1; i <= N; i++) {
		int a;
		cin >> a;
		num[i] = a % 2;
	}
}

void solve() {
	dp[0][0] = 1;
	dp[1][0] = 0;

	for (int i = 1; i <= N; i++) {
		if (num[i]) {
			dp[0][i] = dp[1][i] = dp[0][i - 1] + dp[1][i - 1];
		}
		else {
			dp[0][i] = 2 * dp[0][i - 1];
			dp[1][i] = 2 * dp[1][i - 1];
		}
	}
	cout << dp[P][N] << endl;
}


int main() {
	input();
	solve();

	return 0;
}

Measured memory_bytes: 256
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        a: i64,
        b: i64,
        c: i64,
    }

    if a<=c && c<=b {
        println!("Yes");
    } else {
        println!("No");
    }

}


Measured memory_bytes: 2128
def resolve():
  l = list(map(int, input().split()))
  l.sort()
  a, b, c = l[0], l[1], l[2]
  ans = 0
  ans += c - b
  a += ans
  while a < c:
    a += 2
    ans += 1
  if a > c:
    ans += 1
  print(ans)

  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Calc calc = new Calc();
		int[] height = {0,0,0};
		int newh;
		;
		for(int cnt = 0;cnt<10;cnt++){
			newh = sc.nextInt();
			height = Calc.calc(newh, height);
		};
		System.out.println(height[0]);
		System.out.println(height[1]);
		System.out.println(height[2]);
	}
}

class Calc{
	//private static final int imax = 110;
	public static int[] calc(int h, int[] Pastheight){
		int Newheight[] = (int[])Pastheight.clone();
		if( (h > Pastheight[2]) && (h <= Pastheight[1])){
			Newheight[2] = h;
		}else if((h > Pastheight[1]) && (h <= Pastheight[0])){
			Newheight[1] = h;
			Newheight[2] = Pastheight[1];
		}else if(h > Pastheight[0]){
			Newheight[0] = h;
			Newheight[1] = Pastheight[0];
			Newheight[2] = Pastheight[1];
		}
	return Newheight;
	}
}

Measured memory_bytes: 26024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define For(a, b, c) for(int a = b; a <= c; ++a)
#define Ford(a, b, c) for(int a = b; a >= c; --a)
#define All(a, b) for(auto &a : b)
#define Rep(a, b, c) for(int a = b; a < c; ++a)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
#define reset(a, b) memset(a, b, sizeof(a))
#define bit(x, i) (x >> (i - 1) & 1ll)
#define onbit(x, i) (x | (1ll << (i - 1)))
#define offbit(x, i) (x & ~(1ll << (i - 1)))
#define bitone(i) __builtin_popcountll(i)
#define bitl(i) __builtin_clz(i)
#define bitr(i) __builtin_ctz(i)
#define vll vector<ll>
/********************************************************

Digvijay Bahadur Singh
MNNIT

*********************************************************/
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}


const int MOD=1e9+7;
const int N = 1e6+100;
/********************************************************************/
                 /* GRAPH*/
//vector<vector<ll>> g;
//vector<bool> vis1,vis2;
/*******************************************************************/
ll power(ll a,ll b)
{
   ll ans =1;
   while(b>0){
   if(b&1) ans = (ans%MOD * a%MOD)%MOD;
   a = (a%MOD * a%MOD)%MOD;
   b=b>>1;
   }
   return ans%MOD;
}


signed main(){
  ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
  ll n;

  
  ll T=1;
 // cin>>T;
  
   // T=1;
    
        while(T--)
        {
          int n;
          cin>>n;
          int x=n/500;
          n-=x*500;
          int ans=0;
          ans+=x*1000;
          x=n/5;
          ans+=x*5;
          cout<<ans<<"\n";
        }
    
      

  }

  



Measured memory_bytes: 256
N = gets.chomp.to_i
Ls = gets.chomp.split.map(&:to_i)

count = 0
0.upto(N-3){ |i|
  (i+1).upto(N-2){ |j|
    (j+1).upto(N-1){ |k|
      if [Ls[i], Ls[j], Ls[k]].uniq.size == 3
        min2 = [Ls[i], Ls[j], Ls[k]].min(2)
        max = [Ls[i], Ls[j], Ls[k]].max
        if min2.sum > max
          #p [Ls[i], Ls[j], Ls[k]]
          #p [i+1, j+1, k+1]
          count += 1
        end
      end
    }
  }
}

puts count


Measured memory_bytes: 14564
#pragma GCC optimize("O3")

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
tree<int,int,greater<int>,rb_tree_tag,tree_order_statistics_node_update> map_t;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define sz(x) (int)x.size()
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define REV(x) reverse(x.begin(),x.end())
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
const ll MOD=1000000007;
const int mxN=2e5+5;
int n;
map<pair<ll,ll>,int> cnt;

ll mul(ll a,ll b) {
    a=(a%MOD+MOD)%MOD;
    b=(b%MOD+MOD)%MOD;
    return (a*b)%MOD;
}

ll modpow(ll a,ll b) {
    a=(a%MOD+MOD)%MOD;
    if(!b)
        return 1;
    ll res=modpow(a,b/2);
    if(b%2)
        return mul(a,mul(res,res));
    return mul(res,res);
}

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    int az=0,bz=0,zz=0;
    F0R(i,n) {
        ll a,b;
        cin >> a >> b;
        if(!a && !b) {
            zz++;
            continue;
        }
        if(!a) {
            az++;
            continue;
        }
        if(!b) {
            bz++;
            continue;
        }
        ll gcd=__gcd(a,b);
        a/=gcd;
        b/=gcd;
        if(a<0) {
            a*=-1;
            b*=-1;
        }
        cnt[{a,b}]++;
    }
    n-=zz+bz+az;
    multiset<pair<int,int>> groups;
    ll su=0; 
    set<pair<ll,ll>> vis;
    ll tot=1;
    for(auto p : cnt) {
        if(vis.find(p.first)!=vis.end())
            continue;
        pair<ll,ll> rat=p.first;
        pair<ll,ll> irat={-p.first.second,p.first.first};
        if(irat.first<0) {
            irat.first*=-1;
            irat.second*=-1;
        }
        vis.insert(rat);
        vis.insert(irat);
        if(cnt.find(irat)==cnt.end())
            continue;
        groups.insert({cnt[rat],cnt[irat]});
        su+=cnt[rat]+cnt[irat];
    }
    groups.insert({az,bz});
    tot=modpow(2,n-su);
    for(auto p : groups)
        tot=mul(tot,modpow(2,p.first)+modpow(2,p.second)-1);
    tot=(tot+zz-1+MOD)%MOD; 
    cout << tot;

    return 0;
}


Measured memory_bytes: 41040
#import<iostream>
int m[]={2189,89,1232,866,1796,2603},a,b,c,d,r;int main(){for(char s[9];std::cin>>s;r+=a%3?b%3?(b+6-a)%6<3?2:5:3+!b:a?6:1)*s<65?r&&printf("%d\n",r),a=c=r=0,b=1:*s%6-4?d=(*s-78?*s%5-1:0)+c&3,a=m[a]>>3*d&7,b=m[b]>>3*d&7:c+=3+*s;}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef bool boool;
typedef long long ll;
#define vl vector<ll>
#define vb vector<boool>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define vvp vector<vector<pair<ll, ll>>>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define rep1(i, n) for (long long i=0; i<(long long)(n); i++)
#define rep2(i, s, e) for (long long i=(s); i<(long long)(e); i++)
#define GET_MACRO(_1,_2,_3,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

int main(){
  int n, x, t;
  cin >> n >> x >> t;
  int sum = 0;
  int time = 0;
  for(int i=1; i<=1000; i++){
    sum += x;
    time += t;
    if(sum >= n){
      cout << time << endl;
      return 0;
    }
  }
}
    
    
    

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
static const int64_t mod=1000000007;
int64_t f(int64_t x,int64_t y){
if(y==0)
  return 1;
  else if(y%2==0)
    return (f(x,y/2)*f(x,y/2))%mod;
  else
    return (x*((f(x,y/2)*f(x,y/2))%mod))%mod;
}
int main(){
 int64_t N,M;
  cin>>N>>M;
  int64_t a=1;
  for(int64_t i=M;M-N+1<=i;i--)
    a=(a*i)%mod;
  int64_t ans=0;
  int64_t c=1;int64_t d=a;
  for(int64_t i=0;i<=N;i++){
  ans=(ans+c*d)%mod;
    c=(c*(N-i))%mod;c=(c*f(i+1,mod-2))%mod;
    c=(mod-c)%mod;
    d=(d*f(M-i,mod-2))%mod;
  }ans=(ans*a)%mod;
  cout<<ans<<endl;
  return 0;
}

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

int main() {
  int A, B;
  
  cin >> A >> B;
  int ans;
  
  if(A <= 2 * B) ans = 0;
  else ans = A-2*B;
  
  cout << ans << endl;
  

}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define N 200000000
#define INF 2000000001
  
int size;
int h[N];
  
void swap(int* a, int* b){
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
  
void maxHeapify(i){
  int l = 2*i;
  int r = 2*i+1;
  int valM;
  if(l <= size && h[l] > h[i]) valM = l;
  else valM = i;
  if(r <= size && h[r] > h[valM]) valM = r;
  if(valM != i){
    swap(&h[i], &h[valM]);
    maxHeapify(valM);
  }
}
  
void hIncreaseKey(int i, int key){
  if(key < h[i]) return;
  h[i] = key;
  while(i>1 && h[i/2]<h[i]){
    swap(&h[i], &h[i/2]);
    i = i/2;
  }
}
  
void maxHeapInsert(int key){
  size++;
  h[size] = -INF;
  hIncreaseKey(size, key);
}
  
int heapExtractMax(){
  int valM;
  if(size < 1) return 0;
  valM = h[1];
  h[1] = h[size--];
  maxHeapify(1);
  return valM;
}
  
int main(){
  char input[20];
  size = 0;
  while(scanf("%s", input)){
    if(!strcmp(input, "end")) break;
    if(!strcmp(input, "extract")) printf("%d\n", heapExtractMax());
    else{
      char val[20];
      scanf("%s", val);
      maxHeapInsert(atoi(val));
    }
  }
  return 0;
}

Measured memory_bytes: 4636
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[1000010];
ll kai[1000010];
ll beki(ll n,ll k){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=mod;
    }
    now*=now;
    now%=mod;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n){
  return beki(n,mod-2);
}
void nckinit(ll n){
  kai[0]=1;
  kai[1]=1;
  for(int i=2;i<=n;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=mod;
  }
  gya[n]=gyaku(kai[n]);
  for(int i=n-1;i>=1;i--){
    gya[i]=gya[i+1]*(i+1);
    gya[i]%=mod;
  }
  gya[0]=1;
}
ll nck(ll n,ll k){
  if(k<0)return 0;
  if(k==0||n==k)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=mod;
  ret*=gya[k];
  ret%=mod;
  return ret;
}
ll npk(ll n,ll k){
  if(k<0)return 0;
  if(k==0)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=mod;
  return ret;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    ll x,y;cin>>x>>y;
    if((x+y)%3!=0){
        cout<<0<<endl;
        return 0;
    }
    ll k=(x+y)/3;
    ll a=(2*x-y)/3;
    if(a<0||a>k){
        cout<<0<<endl;
        return 0;
    }
    nckinit(1000001);
    ll ans=nck(k,a);
    cout<<ans<<endl;
}


Measured memory_bytes: 15872
#include<iostream>
#include<queue>
#include<bitset>
#include<algorithm>
#include<climits>
#include<vector>
#include<deque>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> P;
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define dump(a) rep(i,a.size()){ cout<<a[i]<<" "; } cout<<endl;
#define dumparr(a,n) rep(i,n){ cout<<a[i]<<" "; } cout<<endl;
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define INF INT_MAX/3
#define FINF DBL_MAX/3
#define EPS 1e-7

/*
 *
 */

int main(){
  ll k;
  cin>>k;
  if(k%2==0){
    cout<<(k/2)*(k/2)<<endl;
  }else{
    cout<<(k/2)*((k/2)+1)<<endl;
  }
  return 0;
}


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

int main(){
    int N;
    cin >> N;
    int a = N%10;
    string ans;
    if(a == 2 or a == 4 or a == 5 or a == 7 or a == 9){
        ans = "hon";
    }
    else if(a == 0 or a == 1 or a == 6 or a == 8){
        ans = "pon";
    }
    else{
        ans = "bon";
    }

    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <cctype>
#include <stdio.h>
using namespace std;

int main(){
  string s,p;
  cin >> s >> p;

  string t = s + s;
  int n=0;

  for(int i=0;i<t.size();i++){
    for(int j=0;j<p.size();j++){
      if(t[i]!=p[j]){
        break;
      }else{
        for(int k=0;k<p.size();k++){
          if(t[i+k] == p[j+k]){
            n++;
          }else if(n==p.size()){
            break;
          }else{
            n=0;
            break;
          }
        }
      }
      if(n==p.size())
        break;
    }
    if(n==p.size())
      break;
  }

  if(n == p.size()){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  //cout << t << endl;

  return 0;
}



Measured memory_bytes: 3216
#include <iostream>
#include <vector>

using namespace std;

long long dp[3100][3100];
//int dp[30][30];


int main(){
    int N;
    cin >> N;
    vector<int> a(N);

    for(int i=0; i<N; ++i){
        cin >> a[i];
    }

    for(int i=0; i <N; ++i){
        dp[i][i] = 0;
    }

    for(int len =1; len <=N; ++len){
        for(int i=0; i+len <= N; ++i){
            int j = i + len;

            //first
            if( (N-len)%2 == 0 ){
                //int one = dp[i+1][j] +a[i];
                //int two = dp[i][j-1] + a[j-1];
                dp[i][j] = max(dp[i+1][j] +a[i], dp[i][j-1] + a[j-1] );
            }else{
            //second
                //int one = dp[i+1][j] -a[i];
                //int two = dp[i][j-1] - a[j-1];
                dp[i][j] = min(dp[i+1][j] -a[i], dp[i][j-1] - a[j-1] );
            }
        }
    }

    cout << dp[0][N] << endl;
}

Measured memory_bytes: 73984
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 3e3 + 5, mod = 1e9 + 7;

ll a[N][N], dp[N][N][4];
int mark[N][N][4], n, m, k;

ll solve(int r, int c, int kam){
    if(r >= n || c >= m || kam >= 3) return 0;
    if(mark[r][c][kam]) return dp[r][c][kam];
    mark[r][c][kam] = 1;
    ll op1 = a[r][c] + solve(r, c + 1, kam + 1);
    ll op2 = solve(r, c + 1, kam);
    ll op3 = a[r][c] + solve(r + 1, c, 0);
    return dp[r][c][kam] = max({op1, op2, op3});
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < k; i++){
        int x, y, val;
        cin >> x >> y >> val;
        x--;
        y--;
        a[x][y] = val;
    }
    cout << solve(0, 0, 0);

    return 0;
}


Measured memory_bytes: 496900
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#pragma region Macros
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
#define LAST(X) X[X.size()-1]
#define MOD 1000000007
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
inline bool BETWEEN(int x, int min,int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}

using namespace std;
#pragma endregion
signed main() {
	int N,K,X,Y;
	int O;
	cin >> N >> K >> X >>Y;
	cout << min(N, K) * X + max(O, N - K) * Y;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair<int,int> , null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update> 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
// #define endl '\n'
#define int int64_t
#define double long double
#define fdt fuck donald trump
mt19937 rnd(time(0));
const int MAXN = 100001;

int n, m;
int a[MAXN];

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
	// freopen("FDT.txt","r",stdin);
	cin >> n >> m;
	int sum = 0;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		sum += a[i];
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= m; i ++)
		if(a[n - i + 1]*m*4 < sum){
			cout << "No";
			return 0;
		}
	cout << "Yes";
}


Measured memory_bytes: 256