akhauriyash/Code-Regression huggingface dataset:
#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 n;
    cin >> n;
    vector<int> a(n);
    int x;
    for(int i = 0; i < n; i++) {
        cin >> x;
        a[i] = x - i;
    }

    sort(a.begin(), a.end());
    int b = a[(n - 1) / 2];
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += abs(a[i]-b);
    }

    cout << ans << endl;

    return 0;
}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define reps(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end()))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

signed main() {
    int N;
    cin >> N;
    vint V(N + 1), W(N + 1);
    reps(i, N) { cin >> V[i] >> W[i]; }
    int m = min(bit(9) - 1, N);
    vvint dp(m + 1, vint(110000));
    reps(i, m) {
        rep(j, 110000) {
            chmax(dp[i][j], dp[i / 2][j]);
            if (j >= W[i]) { chmax(dp[i][j], dp[i / 2][j - W[i]] + V[i]); }
        }
    }
    int Q;
    cin >> Q;
    rep(i, Q) {
        int v, L;
        cin >> v >> L;
        vint Vc, Wc;
        while (v >= m) { Vc.push_back(V[v]), Wc.push_back(W[v]), v >>= 1; }
        int ans = 0;
        rep(j, bit(Vc.size())) {
            int Vsum = 0, Wsum = 0;
            rep(k, Vc.size()) { if (j & bit(k)) { Vsum += Vc[k], Wsum += Wc[k]; }}
            if (Wsum > L) { continue; }
            chmax(ans, dp[v][L - Wsum] + Vsum);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 448588
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  string s[n + 1];
  s[n] = " ";
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  sort(s, s + n);
  int max, m;
  max = 0;
  m = 1;
  for (int i = 0; i < n; i++) {
    if (s[i] == s[i + 1]) {
      m++;
    } else {
      if (max < m) {
        max = m;
      }
      m = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == s[i + 1]) {
      m++;
    } else {
      if (max == m) {
        cout << s[i] << endl;
      }
      m = 1;
    }
  }
  return 0;
}


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

int main(){
  vector<int> n(3); cin>>n[0]>>n[1]>>n[2];
  sort(n.begin(),n.end());
  if(n[0]==5 && n[1]==5 && n[2]==7) cout <<"YES" << endl;
  else cout << "NO" << endl;
}

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

//#define int ll
#define pb push_back
#define DBGB if (false)

using ll=long long;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vpii=vector<pii>;
using vvpii=vector<vpii>;


void dfsmark(const vvpii& origg, vi& vis, vi& reach0, int currv) {
    vis[currv] = 1;
    reach0[currv] = 1;
    for (const auto& p: origg[currv]) {
        int w, c;
        tie(w, c) = p;
        if (!vis[w])
            dfsmark(origg, vis, reach0, w);
    }
}

void dfs(const vvpii& revg, vvpii& g, vi& vis, const vi& reach0, int currv) {
    vis[currv] = 1;
    for (const auto& p: revg[currv]) {
        int w, c;
        tie(w, c) = p;
        if (!vis[w])
            dfs(revg, g, vis, reach0, w);
        if (reach0[w])
            g[w].pb({currv, c});
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, p;
    cin >> n >> m >> p;
    
    vvpii revg(n);
    vvpii origg(n);
    for (int i=0; i<m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        c -= p;
        revg[b].pb({a, -c});
        origg[a].pb({b, -c});
    }

    vvpii g(n);
    vi vis(n, 0);
    vi reach0(n, 0);
    dfsmark(origg, vis, reach0, 0);
    assert(reach0[n-1]);
    vis = vi(n, 0);
    dfs(revg, g, vis, reach0, n-1);
    assert(vis[0]);

    vll dist(n, 1e16);
    dist[0] = 0;
    for (int i=0; i<n-1; ++i) {
        for (int v=0; v<n; ++v) {
            for (auto p: g[v]) {
                if (dist[v] + p.second < dist[p.first]) {
                    dist[p.first] = dist[v] + p.second;
                    //cerr << "dbg rel " << v << " " << p.first << " " << p.second << ": " << dist[p.first] << endl;
                }
            }
        }
    }
    bool negcyc = false;
    for (int v=0; v<n; ++v) {
        for (auto p: g[v]) {
            if (dist[v] + p.second < dist[p.first])
                negcyc = true;
        }
    }

    if (negcyc)
        cout << "-1\n";
    else
        cout << max(0ll, -dist[n-1]) << "\n";
}


Measured memory_bytes: 896
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF (long long)(1e18)
#define MOD (int)(1e9+7)
#define MAX_N 103
#define MAX_V 10
#define MAX_M 101
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define yn(f) (f?"Yes":"No")
#define YN(f) (f?"YES":"NO")
#define pro "はいプロ　世界一○○が上手　○○界のtourist　○○時代の終焉を告げる者　実質○○　○○するために生まれてきた男"

signed main(){
	cout<<fixed<<setprecision(7);
	int a, b, c, d, n, m;
	string s, t;
	bool flag = false, f = true;
	int e, r, g;
	
	// cin>>n>>m;
	
	cin>>r>>g;
	
	cout<<2*g-r<<endl;
	
	// cout<<yn(f)<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

const int MAXN=111;

int N;
int Vis[MAXN];

int main(){
	
	cin >> N;
	for(int i=0;i<=N;++i)	if(i%4==0)	Vis[i]=true;
	for(int i=0;i+7<=N;++i)	Vis[i+7]|=Vis[i];
	if(Vis[N])	cout << "Yes" << endl;
	else	cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <numeric>
#include <set>
// #include <bits/stdc++.h>


using namespace std;
typedef long long li;

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

    li n;
    cin >> n;
    vector<li> as(n);
    li possums[2] = {};
    bool allneg = true;
    for (int i = 0; i < n; ++i) {
        li x;
        cin >> x;
        as[i] = x;
        allneg &= x <= 0;
        possums[i & 1] += max(x, 0LL);
    }

    if (allneg) {
        li maxpos = max_element(as.begin(), as.end()) - as.begin();
        cout << as[maxpos] << endl;
        cout << n - 1 << endl;
        for (int i = n - 1; i > maxpos; --i) {
            cout << i + 1 << endl;
        }
        for (int i = 0; i < maxpos; ++i) {
            cout << 1 << endl;
        }
        return 0;
    }

    vector<li> ops;
    vector<bool> want(n, false);
    auto omit = [&](int i) {
        ops.push_back(i);
        as.erase(as.begin() + i);
        want.erase(want.begin() + i);
    };


    li mask = possums[0] < possums[1];
    for (int i = 0; i < as.size(); ++i) {
        want[i] = ((i & 1) == mask) && as[i] > 0;
    }

    while (!want.front()) {
        omit(0);
    }

    while (!want.back()) {
        omit(as.size() - 1);
    }

    while (as.size() > 1) {
        for (int i = 1; i < as.size() - 1; ++i) {
            if (want[i]) {
                continue;
            }
            if (want[i - 1] == want[i + 1]) {
                as[i - 1] += as[i + 1];
                as.erase(as.begin() + i + 1);
                want.erase(want.begin() + i + 1);
                omit(i);
                break;
            }
        }
    }

    cout << as.front() << endl;
    cout << ops.size() << endl;
    for (int i = 0; i < ops.size(); ++i) {
        cout << ops[i] + 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vector<int>>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define pii pair<int, int>
#define vpli vector<pair<long long, int>>
#define deb(x) cout << "deb " << #x << " " << x << endl;
#define all(x) x.begin(), x.end()
#define endl "\n"
const ll BIG = 1e18;

void swap(ll &a, ll &b)
{
    ll t = a;
    a = b;
    b = t;
}

ll Min(ll a, ll b, ll c)
{
    return min(a, min(b, c));
}

void printvec(vi &vec)
{
    for (int x : vec)
    {
        cout << x << " ";
    }
    cout << endl;
}

int sum(int a)
{
    int ans = 0;
    while (a)
    {
        ans += (a % 10);
        a = a / 10;
    }
    return ans;
}
void print(vi &mp)
{
    for (auto x : mp)
    {
        cout << x;
    }
    cout << endl;
}
void solve()
{
    int n;
    cin>>n;
    vi a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    sort(all(a));
    sort(all(b));
    if(n%2)
    {
        cout<<(b[n/2]-a[n/2]+1)<<endl;
    }
    else
    {
        cout<<(b[n/2]+b[n/2-1]-a[n/2]-a[n/2-1] + 1)<<endl;
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 4784
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N, T = in.nextInt
  case class Route(cost: Int, time: Int)
  val routes = List.fill(N)(Route(in.nextInt, in.nextInt))
  println(routes.filter(_.time <= T) match {
    case Nil => "TLE"
    case l => l.minBy(_.cost).cost
  })
}

Measured memory_bytes: 25664
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans,a,b,c,d,tmp[3],tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>tmp[0]>>tmp[1]>>tmp[2];
    sort(tmp,tmp+3);
    Cout(tmp[0]*tmp[1]/2);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <map>
#include <iomanip>
using namespace std;

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

    long int count = 0;
    for (int i = 1; i < N; i++) {
    	count += (N-1)/i;
    }
	cout << count << endl;

    return 0;
}

Measured memory_bytes: 3644
(n, k) = map(int, input().split(" "))

xs = []
ys = []
pts = []
for _ in range(n):
    (x, y) = map(int, input().split(" "))
    xs += [x]
    ys += [y]
    pts += [(x, y)]

xs.sort()
ys.sort()

res = float("inf")
for a in xs:
    for b in xs:
        ci = 0
        di = 1
        while di < len(ys):
            num = 0
            c = ys[ci]
            d = ys[di]
            
            for x in pts:
                if a <= x[0] <= b and c <= x[1] <= d:
                    num += 1
        
            if num >= k:
                res = min(res, abs(b-a)*abs(d-c))
                if ci < di:
                    ci += 1
                else:
                    di += 1
            else:
                di += 1

print(res)

Measured memory_bytes: 3064
import Data.Char (isSpace)
import Data.Int (Int64)
import Data.List (unfoldr)
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as BS
import Control.Monad (replicateM)

main = do
  [n,maxW] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  items <- replicateM n $ do
    [w,v] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (w, fromIntegral v :: Int64)
  print $ solve maxW items U.! maxW

solve :: Int -> [(Int, Int64)] -> U.Vector Int64
solve maxW [] = U.replicate (maxW + 1) 0
solve maxW ((w,v):xs)
  = let a = solve maxW xs
    in U.generate (maxW + 1)
       $ \i -> if w <= i
               then max (a U.! i) (a U.! (i - w) + v)
               else a U.! i


Measured memory_bytes: 81916
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6;
#define debug(x) cerr << "[(" << __LINE__ << ") " << (#x) << "]: " << x << endl;

int32_t main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s , ss;
    cin >> s >> ss;
    int c = 0;
    for(int i = 0 ; i < 3 ; i++){
        c += (s[i] == ss[i]);
    }
    cout << c << endl;

    return 0;
}


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


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

    int answer = N / (2*D + 1);
    if(N % (2*D+1) == 0){
        cout << answer;
    }
    else{
        cout << answer + 1;
    }
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization.Formatters;
using static System.Console;
using static System.Math;

namespace YukiCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve();
        }

        public void Solve()
        {
            string S = ReadLine();
            int cnt = 0;
            
            for (int i = 0; i < S.Length/2; i++)
            {
                if (S[i] != S[S.Length - 1 - i])
                {
                    cnt++;
                }
            }

            Console.WriteLine(cnt);

        }
    }
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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


int N;
double dp[3005][3005];
double p[3005];

void solve() {
    cin >> N;
    rep(i, N) cin >> p[i];

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1.0;
    rep(i, N){
        rep(j, N){
            dp[i+1][j+1] += dp[i][j]*p[i];
            dp[i+1][j] += dp[i][j]*(1-p[i]);
        }
    }

    double res = 0.0;
    Rep1(i, (N+1)/2, N) res += dp[N][i];

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 74880
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using ull=unsigned long long int;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
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;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
ll n,m,t;
cin>>n>>m>>t;
V<ll> a(n+1);
a[0]=-m;
for(int i=1;i<=n;i++)cin>>a[i];
a.emplace_back(t+m);
ll ans=0;
for(int i=0;i<=n;i++){
  if(a[i+1]-a[i]>=2*m)ans+=a[i+1]-a[i]-2*m;
}
cout<<ans<<"\n";
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
#define MS(x, i) memset(x, i, sizeof x)
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define NOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

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

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
char F[200];

inline ll read() {
    ll ret = 0, sgn = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') sgn = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ret = ret*10 + ch - '0';
        ch = getchar();
    } 
    return ret*sgn;
}

inline void write( ll x ) {
    ll tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0) {
       F[cnt++] = tmp % 10 + '0';
       tmp /= 10;
    }
    while(cnt > 0) putchar(F[--cnt]);
}

int main()
{
    NOS
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    string a, b;
    cin >> a >> b;

    if(a == b.substr(0, a.length()))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

    return 0;
}

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

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ALL(a) begin(a), end(a)
#define SZ(a) ((int)(a).size())

#define REP(a, b) for (int a = 0; a < (b); a++)
#define FOR(a, b, c) for (int a = (b); a <= (c); a++)
#define REPD(a, b) for (int a = (b) - 1; a >= 0; a--)
#define FORD(a, b, c) for (int a = (b); a >= (c); a--)

#define MIN(a, b) (a) = min((a), (b))
#define MAX(a, b) (a) = max((a), (b))

#ifdef __DEBUG
#define debug if (true)
#else
#define debug if (false)
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2> &p) {
  return is >> p.fi >> p.se;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  VV<int> mat(n, vi(n));
  REP(i, n) REP(j, n) cin >> mat[i][j];
  V<ll> sum(1 << n);
  REP(mask, (1 << n)) {
    REP(i, n) REP(j, i) if ((mask >> i & 1) && (mask >> j & 1)) sum[mask] += mat[i][j];
  }
  V<ll> dp(1 << n);
  REP(i, 1 << n) {
    dp[i] = sum[i];
    for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
      MAX(dp[i], dp[j] + dp[i ^ j]);
    }
  }
  cout << dp[(1 << n) - 1] << endl;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main() {
    IOS;
	ll n;
	cin>>n;
	ll f[110]={};
	rep(i,n) {
		rep(j,10) {
			ll a;
			cin >> a;
			f[i] += a << (9 - j);
		}
	}
	ll p[n][11];
	rep(i,n) {
		rep (j,11) {
			cin >> p[i][j];
		}
	}
	int ans = -1e9;
	for (int i = 1;i < 1024;i++) {
		int cost = 0;
		for (int j = 0;j < n;j++) {
			cost += p[j][__builtin_popcount(f[j] & i)];
		}
		ans = max(ans, cost);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import heapq

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

heapq.heapify(vs)

while len(vs) >= 2:
    t1 = heapq.heappop(vs)
    t2 = heapq.heappop(vs)
    value = (t1 + t2) / 2
    heapq.heappush(vs, value)

print(vs[0])


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
 
#define rep(i, a, b) for(ll (i) = (a); (i) < (b);++i)
 
ll gcd(ll x, ll y)
{
  if (x % y == 0)
  {
    return y;
  }
  return gcd(y, x % y);
}
 
int main()
{
  ll a, b;
  cin >> a >> b;
  if ((a + b) % 3 == 0 || a % 3 == 0 || b % 3 == 0){
    cout << "Possible" << endl;
  }else{
    cout << "Impossible" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
md=10**9+7
t=1
# t=int(input())

for some_num in range(0,t):
    n=int(input())
    vals=[int(i) for i in input().split(" ")]

    s=0
    for i in range(0,n):
        s=(s+vals[i])%md

    csum=0

    for i in range(0,n-1):
        s-=vals[i]

        csum= (csum+vals[i]*s)%md

    print(csum)

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
ll nxt(){ll x;cin>>x;return x;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,p;
    cin>>n>>p;
    string st;
    cin>>st;
    ll ans=0;
    if(p==2||p==5){
        forn(i,n){
            if((st[i]-'0')%p==0) ans+=i+1;
        }
    }else{
        vector<int> d(n+1);
        for(int i=n-1,ten=1;i>=0;i--){
            int a=(st[i]-'0')*ten%p;
            d[i]=(d[i+1]+a)%p;
            (ten*=10)%=p;
        }
        vector<int> cnt(p);
        for(int i=n;i>=0;i--){
            ans+=cnt[d[i]];
            cnt[d[i]]++;
        }
    }
    cout<<ans;
}



Measured memory_bytes: 1428
n = int(input())
a = [int(i) for i in input().split()]
color = [0] * 8
any = 0
for i in a:
    if 1 <= i <= 399:
        color[0] = 1
    elif 400 <= i <= 799:
        color[1] = 1
    elif 800 <= i <= 1199:
        color[2] = 1
    elif 1200 <= i <= 1599:
        color[3] = 1
    elif 1600 <= i <= 1999:
        color[4] = 1
    elif 2000 <= i <= 2399:
        color[5] = 1
    elif 2400 <= i <= 2799:
        color[6] = 1
    elif 2800 <= i <= 3199:
        color[7] = 1
    else:
        any += 1
m = max(sum(color), 1)
M = sum(color) + any
print(m, M)

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

int a[100005];

int main() {
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++) scanf("%d",a+i);
  sort(a,a+n);
  int x = a[--n], y = a[0], z = abs(x-y*2);
  for(int i=1;i<n;i++) {
    int tmp = abs(x-a[i]*2);
    if(tmp < z) {
      z = tmp;
      y = a[i];
    }
  }
  printf("%d %d\n",x,y);
}


Measured memory_bytes: 640
#!/usr/bin/ruby
h={2=>[[2, 1]], 3=>[[3, 1]], 4=>[[2, 2]], 5=>[[5, 1]], 6=>[[2, 1], [3, 1]], 7=>[[7, 1]], 8=>[[2, 3]], 9=>[[3, 2]], 10=>[[2, 1], [5, 1]], 11=>[[11, 1]], 12=>[[2, 2], [3, 1]], 13=>[[13, 1]], 14=>[[2, 1], [7, 1]], 15=>[[3, 1], [5, 1]], 16=>[[2, 4]], 17=>[[17, 1]], 18=>[[2, 1], [3, 2]], 19=>[[19, 1]], 20=>[[2, 2], [5, 1]], 21=>[[3, 1], [7, 1]], 22=>[[2, 1], [11, 1]], 23=>[[23, 1]], 24=>[[2, 3], [3, 1]], 25=>[[5, 2]], 26=>[[2, 1], [13, 1]], 27=>[[3, 3]], 28=>[[2, 2], [7, 1]], 29=>[[29, 1]], 30=>[[2, 1], [3, 1], [5, 1]], 31=>[[31, 1]], 32=>[[2, 5]], 33=>[[3, 1], [11, 1]], 34=>[[2, 1], [17, 1]], 35=>[[5, 1], [7, 1]], 36=>[[2, 2], [3, 2]]}
while true
	l=gets.split
	n=l[0].to_i;m=l[1].to_i(n)
	if n==0 then break end
	p h[n].map{|a,b|
		z=m
		r=0
		while z>0 do
			r+=(z/=a)
		end
		r/b
	}.min
end

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

void solve() {
	int n, x, t, ans;
	cin >> n >> x >> t;
	ans = t * ((int)((n - 1) / x) + 1);
	cout << ans << endl;
}

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

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

int main() {
    int n;
    cin >> n;
    vector<pair<ll, int>> a(n);
    rep(i,n){
        ll x;
        cin >> x;
        a[i] = make_pair(x, i);
    }
    sort(a.rbegin(), a.rend());

    vector<vector<ll>> dp(n+1, vector<ll>(n+1, 0));

    ll ans = 0;
    for (int l = 0; l < n; l++) {
        for(int r = 0; r < n; r++){
            if(l+r == n){
                ans = max(ans, dp[l][r]);
                break;
            }
            ll activeness = a[l+r].first;
            int index = a[l+r].second;
            dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] +abs(index - l) * activeness);
            dp[l][r+1] = max(dp[l][r+1], dp[l][r] +abs(index - (n-1-r)) * activeness);
        }
    }
    cout << ans << endl;
}


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


using ll = long long;
int N;
string S;


ll solve()
{
    if (N <= 2) return 0;
    vector<int> vr(N + 1);
    vector<int> vg(N + 1);
    vector<int> vb(N + 1);
    for (int i = N - 1; i >= 0; i--) {
        vr[i] = vr[i + 1] + (S[i] == 'R' ? 1 : 0);
        vg[i] = vg[i + 1] + (S[i] == 'G' ? 1 : 0);
        vb[i] = vb[i + 1] + (S[i] == 'B' ? 1 : 0);
    }
    ll s = 0;
    for (int i = 0; i <= N - 3; i++) {
        for (int j = i + 1; j <= N - 2; j++) {
            if (S[i] == S[j]) continue;
            int k = j + 1;
            if (S[i] != 'R' && S[j] != 'R')
                s += vr[k];
            else if (S[i] != 'G' && S[j] != 'G')
                s += vg[k];
            else
                s += vb[k];
            k = j*2 - i;
            if (k <= N - 1 && S[k] != S[i] && S[k] != S[j]) s--;
        }
    }
    return s;
}


int main()
{
    cin >> N;
    cin >> S;
    ll ans = solve();
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#define ll long long
#define ull unsigned long long

int main()
{
    int m, n;
    std::cin >> n >> m;
    ll sum = 0, count = 0;
    std::vector<int> vec(n);
    for (int i = 0; i < n; ++i)
    {
        std::cin >> vec[i];
        sum += vec[i];
    }
    for (int i = 0; i < n; ++i)
    {
        if (vec[i] >= ((double)sum / (4.0 * m))) { ++count; }
    }
    if (count >= m) { std::cout << "Yes" << std::endl; }
    else
    {
        std::cout << "No" << std::endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,r;
    float x;
    scanf("%d %d", &a,&b);
    if(a>=1&&a<=100&&b>=1&&b<=100)
    {
        x=(a+b)/(float)2;
        r=round(x);
        printf("%d\n",r);
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(true){
    int n; cin>>n;
    if(!n) break;
    int a[10]={};
    for(int i=0;i<n;++i){
      int c;
      cin>>c;
      ++a[c];
    }
    for(int i=0;i<10;++i){
      for(int j=0;j<a[i];++j) cout<<"*";
      if(!a[i]) cout<<"-";
      cout<<"\n";
    }
  }
  return 0;
}



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

string ls="qwertasdfgzxcvb";

int main()
{
	string s;
	while(cin >> s, s!="#")
	{
		bool l=false;
		for(int i=0; i<ls.size(); i++)
			if(ls[i]==s[0]) l=true;

		int ret=0;
		for(int i=1; i<s.size(); i++)
		{
			bool lr=false;
			for(int j=0; j<ls.size(); j++)
			{
				if(ls[j]==s[i]) 
				{
					if(!l) ret++;
					l=true;
					lr=true;
				}
			}
			if(!lr&&l)
			{
				l=false;
				ret++;
			}
		}

		cout << ret << endl;
	}
}

Measured memory_bytes: 0
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = a; i < (b); ++i)
#define REV(i, a, b) for (int i = a; i > (b); --i)
#define debug(a) cerr << #a << " " << a << endl
#define debug2(a, b) cerr << #a << " " << a << ", " << #b << " " << b << endl

using namespace std;
using ll = long long;
using P = pair<int, int>;

void Main() {
  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int a;cin>>a;
    n-=a;
  }
  if (n>=0) cout << n << endl;
  else cout << -1 << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 3656
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> b(n);
    for (int i = 0; i < n; i++) b[i] = a[i] - i;
    std::sort(b.begin(), b.end());

    long res = 0;
    for (int i = 0; i < n; i++) {
        res += std::abs(b[n / 2] - b[i]);
    }
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 1792
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

int main(){
  int N;
  int a[100];
  cin >> N;
  int sum = 0;
  rep(i, N){
    cin >> a[i];
    sum += a[i];
  }

  int ans = 0;
  int min = 100000;
  rep(i, N){
    int v = abs(sum - a[i] * N);
    if(v < min){
      min = v;
      ans = i;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for (int i = 0; i < (n); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    double ds=0;
    ll mul=1;
    rep(i,n){
        ll a;cin >> a;
        if(a==0){
            cout << 0 << endl;
            return 0;
        }
        mul*=a;
        ds+=logf(a);
    }
    ll p=1e18+1e17;
    ll q=1e18;
    if(ds>logf(p)){
        cout << -1 << endl;
    }
    else{
        if(mul>q){
            cout << -1 << endl;
        }
        else{
            cout << mul << endl;
        }
    }
}

Measured memory_bytes: 3892
use std::io;


/// https://beta.atcoder.jp/contests/abc088/tasks/abc088_c
/// Takahashi's Information
/// an = pn + x
/// bn = qn - x
fn main() {
    let c1 = read::<usize>();
    let c2 = read::<usize>();
    let c3 = read::<usize>();
    let c = vec![c1, c2, c3];
    let mut flg = true;
    for i in 0..3 { for j in 0..3 {
    for k in 0..3 { for l in 0..3 {
        if c[i][k] + c[j][l] != c[i][l] + c[j][k] { flg = false; }
    }}
    }}

    if flg { println!("Yes"); }
    else { println!("No"); }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;

ll quickpow(ll n, ll k, ll m)
{
    ll ans = 1, base = n;
    while(k != 0)
    {
        if(k&1)
            ans = ans*base%m;
        base = base*base%m;
        k >>= 1;
    }
    return ans%m;
}

int main()
{
    ll n, k;
    scanf("%lld%lld",&n,&k);
    printf("%lld\n",quickpow(n, k,1000000007));
}



Measured memory_bytes: 3232
#include <bits/stdc++.h>
#define maxs 2020202
#define mme(i,j) memset(i,j,sizeof(i))
using namespace std;
list<int> lt;
list<int>::iterator it;

int main()
{
    int n;
    while(~scanf("%d",&n)){
        int x;
        lt.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(i%2)
                lt.push_back(x);
            else
                lt.push_front(x);
        }

        if(n%2) lt.reverse();

        for(it=lt.begin();it!=lt.end();it++){
            printf("%d ",*it);
        }
        puts("");
    }
    return 0;
}

Measured memory_bytes: 8448
#include <cstdio>
#define rg register
using namespace std;
typedef long long ll;
const int maxn=2010,mod=924844033;
template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> inline void read(Tp &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') f=1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	if(f) x=-x;
}
int n,k,lim,tot,ans,fac[maxn],xu[maxn<<1],link[maxn<<1],f[maxn<<1][maxn][2],g[maxn];
inline int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
void get(int id,int op)
{
	while(id<=n)
	{
		xu[++tot]=id;
		if(op) xu[tot]+=n;
		op^=1;id+=k;
	}
	link[tot]=1;
}
int main()
{
	read(n);read(k);lim=n<<1;fac[0]=1;
	for(rg int i=1;i<=k;i++) get(i,0),get(i,1);
	for(rg int i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
	f[0][0][0]=1;link[0]=1;
	for(rg int i=1;i<=lim;i++)
	  for(rg int j=0;j<=n;j++)
	  {
	  	if(!link[i-1]&&j) f[i][j][1]=f[i-1][j-1][0];
	  	f[i][j][0]=pls(f[i-1][j][0],f[i-1][j][1]);
	  }
	for(rg int i=0;i<=n;i++)
	{
		g[i]=pls(f[n+n][i][0],f[n+n][i][1]);
		if(i&1) ans=dec(ans,(ll)g[i]*fac[n-i]%mod);
		else ans=pls(ans,(ll)g[i]*fac[n-i]%mod);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 62976
#include<bits/stdc++.h>
using namespace std;
char ch[52][52];
long long n,m,b[52][52];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    	  cin>>ch[i][j];
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(ch[i][j]=='.')
        {
        	if(ch[i-1][j-1]=='#')b[i][j]++;
        	if(ch[i-1][j]=='#')b[i][j]++;
        	if(ch[i-1][j+1]=='#')b[i][j]++;
        	if(ch[i][j-1]=='#')b[i][j]++;
        	if(ch[i][j+1]=='#')b[i][j]++;
        	if(ch[i+1][j-1]=='#')b[i][j]++;
        	if(ch[i+1][j]=='#')b[i][j]++;
        	if(ch[i+1][j+1]=='#')b[i][j]++;
        }
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
      {
      	if(ch[i][j]=='.')cout<<b[i][j];
      	else cout<<ch[i][j];
      }
      cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
// 2019/07/06
// AtCoder Beginner Contest 066 - B

#include <bits/stdc++.h>
using namespace std;

int main() {
    int mlen, slen, tflg, widx;
    string s, ans;
    cin >> s;
    slen = s.length() - 1;
    if(slen % 2 == 1){
        slen -= 1;
    }
    while(slen > 1){
        mlen = slen / 2;
        widx = 0;
        tflg = 0;
        while(widx < mlen) {
            if(s[widx] != s[mlen+widx]){
                tflg = 9;
                break;
            }
            widx += 1;
        }
        if(tflg == 0){
            ans = s.substr(0, mlen+widx);
            break;
        }
        slen -= 2;
    }
    cout << ans.length();
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <cstdlib>
#include <map>

using namespace std;

typedef map<string, int> M;
typedef map<string, bool> M2;

int modecule(string str, M mpp, M2 mpp2);
int atom(string str, M mpp, M2 mpp2);
int number(string str);

int p;
bool f;

int modecule(string str, M mpp, M2 mpp2)
{
	int v = 0;
	while(str[p] != ')' && p < str.size()){
		if(str[p] == '('){
			p++;
			int tmp = modecule(str, mpp, mpp2);
			p++;
			tmp *= number(str);
			v += tmp;
		} else if('A' <= str[p] && str[p] <= 'Z'){
			v += atom(str, mpp, mpp2);
		} else {
			f = true;
			return 0;
		}
	}
	
	return v;
}

int atom(string str, M mpp, M2 mpp2)
{
	string s = "";
	s += str[p++];
	int n = 0;
	if('a' <= str[p] && str[p] <= 'z'){
		s += str[p++];
	}
	if(mpp2[s]){
		n = mpp[s];
		n *= number(str);
	} else {
		f = true;
	}
	
	return n;
}

int number(string str)
{
	string s = "";
	int n = 1;
	
	while(isdigit(str[p])){
		s += str[p++];
	}
	if(s.size() > 0){
		n = atoi(s.c_str());
	}
	
	return n;
}

int main()
{
	int n;
	string str;
	
	while(cin>>str>>n){
		M mpp;
		M2 mpp2;
		mpp[str] = n;
		mpp2[str] = true;
		cin>>str;
		while(str != "END_OF_FIRST_PART"){
			cin >> n;
			mpp[str] = n;
			mpp2[str] = true;
			cin >> str;
		}
		
		while(cin>>str && str != "0"){
			p = 0;
			f = false;
			n = modecule(str, mpp, mpp2);
			if(f){
				cout << "UNKNOWN" << endl;
			} else {
				cout << n << endl;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep2(i,start,end) for(int i = start; i < end; i++)
#define ll long long
const ll N = 4e3 + 200;
const ll INF = 0x3f3f3f3f;


int main(){
  int k,x;
  cin>>k>>x;
  int mi = x - k+1;
  for(int i = 0; i < k; i++){
    cout<<mi+i<<" ";
  }
  for(int i = 1; i < k; i++){
    cout<<x+i<<" ";
  }
  return 0;
}


Measured memory_bytes: 256
def main():
    examD()

def examA():
    S = SI()
    if S[-1]=="s":
        ans = S+"es"
    else:
        ans = S+"s"
    print(ans)
    return

def examB():
    N = I()
    D = [LI()for _ in range(N)]
    current = 0
    for d1,d2 in D:
        if d1==d2:
            current += 1
        else:
            current = 0
        if current==3:
            print("Yes")
            return
    print("No")
    return

def examC():
    N = I()
    cnt = 0
    for i in range(1,N):
        for j in range(1,1+N//i-(N%i==0)):
            cnt += 1
    ans = cnt
    print(ans)
    return

def examD():
    N, K = LI()
    LR = [LI()for _ in range(K)]
    dp = [0]*N
    S = [0]*N
    dp[0] = 1
    S[0] = 1
    for i in range(1,N):
        cur = 0
        for l,r in LR:
            if i<l:
                continue
            cur += S[i-l]
            if i<r+1:
                continue
            cur -= S[i-r-1]
            cur += mod2
            cur %= mod2

        dp[i] = cur
        S[i] = S[i-1] + cur
        S[i] %= mod2

    ans = dp[-1]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

typedef unsigned long long ull;

int main(){
#ifdef _DEBUG
	freopen("in" , "r", stdin );
	freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	string s; cin >> s;
	int n = s.size();
	int ans = 0, cnt = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == 'g'){
			if(cnt < n /2){
				cnt++;
				ans++;
			}
		} else {
			if(cnt >= n / 2) ans--;
			else cnt++;
		}
	}
	cout << ans << '\n';
}


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

int main(){
  int N;
  cin >> N;
  
  int c = 0;
  for(int i=0; i<N; i++){
    if(i * 1000 >= N)
      break;
    else
      c++;
  }
  cout << c*1000 - N << endl;
}

Measured memory_bytes: 3596
function Main(input) {
	let inputs = input.split("\n");
	let HW = inputs[0].split(" ").map((n) => (parseInt(n, 10)));
	let H = HW[0];
	let W = HW[1];
	let hw = inputs[1].split(" ").map((n) => (parseInt(n, 10)));
	let h = hw[0];
	let w = hw[1];

	console.log((H-h) * (W-w));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include <iostream>
#include <vector>
#include<string>
using namespace std;
int main(void){

    char A,B;

    
    cin>>A>>B;
    
    if(A>B)
    {
        cout<<">"<<endl;
    }
    else if (A<B)
    {
        cout<<"<"<<endl;
    }
    else cout<<"="<<endl;
    
   
    
    return 0;
}

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

const int MAX_N = 201;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
int N;
int n[MAX_N], d[MAX_N];
int x[MAX_N], y[MAX_N];

int main() {
  while(cin >> N && N) {
    vector<pair<int,int> > Q;
    for(int i = 1; i < N; ++i) {
      cin >> n[i] >> d[i];
      Q.push_back(make_pair(n[i],i));
    }
    sort(Q.begin(),Q.end());
    x[0] = y[0] = 0;
    int sx,sy,ex,ey;
    sx=sy=0;
    ex=ey=1;
    for(int i = 0; i < Q.size(); ++i) {
      int p = Q[i].second;
      x[p] = x[n[p]] + dx[d[p]];
      y[p] = y[n[p]] + dy[d[p]];
      sx = min(sx,x[p]);
      sy = min(sy,y[p]);
      ex = max(ex,x[p]+1);
      ey = max(ey,y[p]+1);
    }
    cout << ex-sx << " " << ey-sy << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(){
    int hours, minites, seconds;
    int time;

    scanf("%d", &time);

    for (hours = 0; time >= 60*60; hours++) {
        time -= 60*60;
    }

    for (minites = 0; time >= 60; minites++) {
        time -= 60;
    }

    seconds = time;

    printf("%d:%d:%d\n", hours, minites, seconds);    

    return 0;
}

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

using namespace std;

using ll = long long;

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

#define INF 1e9

int main(void)
{
    int n, i, a, b, c, t[200000], Max;

    scanf("%d", &n);
    while(n != 0){
        for(i = 0; i < 200000; i++){
            t[i] = 0;
        }

        for(i = 0; i < n; i++){
            scanf("%d:%d:%d", &a, &b, &c);
            t[a * 3600 + b * 60 + c]++;
            scanf("%d:%d:%d", &a, &b, &c);
            t[a * 3600 + b * 60 + c]--;
        }

        Max = t[i];
        for(i = 1; i < 200000; i++){
            t[i] += t[i - 1];
            if(Max < t[i]){
                Max = t[i];
            }
        }

        printf("%d\n", Max);

        scanf("%d", &n);
    }
}


Measured memory_bytes: 3896
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

int main() {
    string s; cin >> s;
    int ans = 0;
    rep(i,3) if (s[i] == '1') ans++;
    cout << ans << endl;
}

Measured memory_bytes: 3628
/*
2020-05-03
atcoder ABC
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int N, M, ans = 0;
    cin >> N >> M;
    vector<ll> data(N);
    vector<vector<int>> bridge(N);
    rep(i, N){
        ll H;
        cin >> H;
        data[i] = H;
    }

    rep(i, M){
        int A, B;
        cin >> A >> B;
        bridge.at(A-1).push_back(B-1);
        bridge.at(B-1).push_back(A-1);
    }

    rep(i, N){
        bool isHighest = true;
        for(int j: bridge.at(i)){
            if(data[i] <= data[j]){
                isHighest = false;
                break;
            }
        }
        if(isHighest){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9016