akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

typedef long long ll;
typedef long double ld;
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPR(i,a,b) for(int i = b; i >= a; i--)
#define all(a)              a.begin(), a.end()
#define alln(a, n)          (a, a+n)
#define sz(x) (int)(x).size()
#define MAX                 10000007
#define MIN                 -10000007
#define pi pair<int,int>
#define pl pair<ll,ll>
#define mii             map<int,int>
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define inf 1e18
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<vi> vvi; 
typedef vector<string> vs;
typedef set<int> si;
const int MOD=1e9+7;
ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
ll gcd(ll a,ll b){return __gcd(a,b);}
ll power(ll a,ll b,ll MOD){if(b == 0)return 1;if(b == 1)return a;ll ans = power(a,b/2,MOD) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
ll inverse(ll x){x%=MOD;return power(x,MOD-2,MOD);}
ll fact[1],inv[1];
void factorial(ll n){
  fact[0]=1;
  for(ll i=1;i<=n;i++){
    fact[i]=fact[i-1]*i;
    if(fact[i]>=MOD)
      fact[i]%=MOD;
  }
}
ll ncr(ll n,ll r){
  if(n<r||n<0||r<0)
    return 0;
  ll b=inv[n-r];
  ll c=inv[r];
  ll a=fact[n]*b;
  if(a>=MOD)
    a%=MOD;
  a*=c;
  if(a>=MOD)
    a%=MOD;
  return a;
}
vector<char> is_prime(100001, true);
void sieve(ll n){
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; i++) {
        if (is_prime[i] && (long long)i * i <= n) {
            for (int j = i * i; j <= n; j += i)
                  is_prime[j] = false;
        }
  }    
}     
 
int main()
{
  ios::sync_with_stdio(0);
    cin.tie(0);
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
      
    int t;
    t=1;
    cout<<fixed<<setprecision(0);
     //  cin>>t;
    while(t--){
            ll a,b,c,d;
            cin>>a>>b>>c>>d;
            vl v;
            v.pb(a*c);
            v.pb(a*d);
            v.pb(b*c);
            v.pb(b*d);
            if(a<=0&&0<=b||c<=0&&0<=d)
              v.pb(0);  
            sort(v.rbegin(),v.rend());
            cout<<v[0];


             }
             cerr<<"Time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int a,b;
  cin>>a>>b;
  if(a<=0 && b>=0){
    puts("Zero");
  }else if(a<0 && b<0 && (b-a+1)%2==1){
    puts("Negative");
  }else{
    puts("Positive");
  }
  return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 1e9
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main() {
  string s;
  int k;
  cin >> k >> s;
  if(s.size()<=k){
    cout << s << endl;
  }else{
    for (int i = 0;i<k;i++){
      cout << s[i];
    }
    cout << "..." << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
import java.io.IOException;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		Map<Integer,Long> map = new HashMap<>();
		int n = sc.nextInt();
		int[] a = new int[n];
		for( int i=0 ; i<n ; i++ ) {
			a[i] = sc.nextInt();
			map.compute( a[i], (k,v)->{ return v==null ? 1 : v+1; } );
		}
		
		int q = sc.nextInt();
		long s=0;
		for( Map.Entry<Integer, Long> it : map.entrySet() ) {
			s+= it.getKey() * it.getValue();
		}

		for( int i=0 ; i<q	 ; i++ ) {
			int b = sc.nextInt();
			int c = sc.nextInt();

			Long bCnt = map.remove(b);
			if( bCnt != null ) {
				s -= b * bCnt;
				s += c * bCnt;
				map.compute( c, (k,v)->{ return v==null ? bCnt : v+bCnt; } );
				
			}

			System.out.println(s);
		}
		
		
		
	}
}

Measured memory_bytes: 66668
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000000
#define MAX 200001

const int MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<MOD>;

int main(){
    int K;
    cin >> K;
    int c = 7;
    ll ans = -1;
    for(int i = 0; i < 1000000; i++){
        if(c % K == 0) {ans = i+1;break;}
        c = c*10+7;
        c %= K;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include <stack>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <iomanip>
#include <string>
#include <limits>
using namespace std;
int gcd(int a, int b)//最大公約数
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
int mod = 1000000000 + 7;
vector<int> v;
class Calc
{
    // 宣言
    long long a;

    public:
        // 素因数分解
        void decompositPrime(long long a);
};

/*
 * 素因数分解
 */
void Calc::decompositPrime(long long n)
{
    // 割る数の初期値
    a = 2;
    // √n ≧ a ( n ≧ a * a ) の間ループ処理
    while (n >= a * a) {
        // a で割り切れたら、a は素因数
        // そして、割られる数を a で割る
        // a で割り切れなかったら、 a を 1 増加させる
        if (n % a == 0) {
            //printf("%d * ", a);
             v.push_back(a);
            n /= a;
        } else {
            a++;
        }
    }
    // 最後に残った n は素因数
    v.push_back(n);
    //printf("%d\n", n);
}
vector<int> divisor(int n) {//約数発見
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    std::sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    //std::stack<int> stack;
    int n;
    cin >> n;
    int ans = 1;
    vector<string> s(n);
    vector<int> cnt(10000000, 0);
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    std::sort(s.begin(), s.end());
    for(int i = 1; i < n; i++){
        if(s[i-1] != s[i]){
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}






Measured memory_bytes: 48652
def div(val):
  ret=[]
  for i in range(1,int(val**0.5)+1):
    if val%i==0:
      ret.append(i)
      if val//i!=i:
        ret.append(val//i)
  return ret

n=int(input())
arr=list(map(int,input().split()))
cnt=[0]*n
num=0
ans=[]
for i in range(n-1,-1,-1):
  if (arr[i]+cnt[i])%2==0:
    continue
  else:
    ans.append(i+1)
    num+=1
    for j in div(i+1):
      cnt[j-1]+=1
if num==0:
  print(0)
else:
  print(num)
  print(*ans)

Measured memory_bytes: 68956
#https://atcoder.jp/contests/dp/tasks/dp_e
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [float("inf")] * (N*1000+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    for j in range(N*1000,-1,-1):
        DP[j] = min(DP[j- v[i]] + w[i], DP[j])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        
        ans = k
print(ans)

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

int main() {
  long long A, B;
  cin >> A >> B;
  
  long long x=0;
  int y=0;
  for (long long i=A; i<=B; i++) {
    if (i<0) {
      x++;
    }
    if (i==0) {
      y++;
    }
  }
  
  if (y==1) {
    cout << "Zero" << endl;
  }
  else if (x%2==1) {
    cout << "Negative" << endl;
  }
  else {
    cout << "Positive" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node {int p, l ,r; };
struct Node T[MAX];
int n;

/* 先行順巡回*/
void preParse(int u) {
    if ( u == NIL ) return;
    printf(" %d", u);
    preParse(T[u].l);
    preParse(T[u].r);
}

/* 中間順巡回*/
void inParse(int u) {
    if ( u == NIL ) return;
    inParse(T[u].l);
    printf(" %d", u);
    inParse(T[u].r);
}

/* 後行順巡回*/
void postParse(int u) {
    if ( u == NIL ) return;
    postParse(T[u].l);
    postParse(T[u].r);
    printf(" %d", u);
}

int main(){
    int i, v, l, r, root;
    scanf("%d", &n);
    for ( i = 0; i < n; i++ ) {
        T[i].p = NIL;
    }
    for ( i = 0; i < n; i++ ) {
        scanf("%d %d %d", &v, &l, &r);
        T[v].l = l;
        T[v].r = r;
        if ( l != NIL ) T[l].p = v;
        if ( r != NIL ) T[r].p = v;
}

for ( i = 0; i < n; i++ ) if ( T[i].p == NIL ) root = i;
    
printf("Preorder\n");
preParse(root);
printf("\n");
printf("Inorder\n");
inParse(root);
printf("\n");
printf("Postorder\n");
postParse(root);
printf("\n");
return 0;

}


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

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++)

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;
    } else {
        return modpow(m, n - 1) * m;
    }
}
typedef long long ll;
typedef pair<ll, ll> P;
map<long long, long long> cnt;
void primeFactors(long long n) {
    while (n % 2 == 0) {
        cnt[2]++;
        n = n / 2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            cnt[i]++;
            n = n / i;
        }
    }
    if (n > 2) {
        cnt[n]++;
    }
}
bool bitcheck(int x, int y) { return (x >> y) & 1; }
signed main() {
    ll d, g;
    cin >> d >> g;
    vector<ll> p(d);
    vector<ll> c(d);
    REP(i, d) {
        cin >> p[i];
        cin >> c[i];
    }
    ll mnproblems = 1000000;
    REP(i, 1 << d) {
        ll sum = 0;
        ll problems = 0;
        REP(j, d) {
            if (bitcheck(i, j)) {
                sum += p[j] * (j + 1) * 100 + c[j];
                problems += p[j];
            }
        }
        for (int j = d - 1; j >= 0; j--) {
          	if(sum >= g) break; 
            if (!bitcheck(i, j)) {
                ll c = min(p[j],(((g - sum + (j + 1) * 100) - 1) / ((j + 1) * 100)));
                problems += c;
              
                sum += c * (j + 1) * 100;
            }
        }
                if (sum >= g) {
                    mnproblems = min(mnproblems, problems);
                }
    }
    cout << mnproblems << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

const int N = 200010;
const int MOD = 1000000007;

vi g[N];
int cnt[N] = {0};

ll fact[N] = {0}, inv[N] = {0}; // for nCr
ll ans[N]; // final ans to print
ll dp[N]; // ans with subtree rooted at i
int par[N];
int n;

ll ffpow(ll a, ll b) {
	if (!b) return 1;
	ll x = ffpow(a, b / 2);
	ll y = (x * x) % MOD;
	if (b % 2) {
		return (a * y) % MOD;
	}
	return y;
}

void pre() {
	fact[0] = 1;
	inv[0] = ffpow(fact[0], MOD - 2);
	for(int i = 1 ; i < N ; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv[i] = ffpow(fact[i], MOD - 2);
	}
}

ll C(ll n, ll r) {
	if (r > n or r < 0) return 0;
	if (r == 0 or r == n) return 1;
	return (((fact[n] * inv[r]) % MOD) * inv[n - r]) % MOD;
}

int dfs(int u, int p=-1) {
	par[u] = p;
	cnt[u] = 1;
	for(int v: g[u]) {
		if (v != p) {
			cnt[u] += dfs(v, u);
		}
	}
	// pdt of dp of children
	// *
	// fact[cnt[u] - 1]
	// /
	// pdt (fact[cnt[v]])
	dp[u] = fact[cnt[u] - 1];
	for(int v: g[u]) {
		if (v != p) {
			dp[u] = (dp[u] * dp[v]) % MOD;
			dp[u] = (dp[u] * inv[cnt[v]]) % MOD;
		}
	}
	return cnt[u];
}

ll get_parent_ans(int i) {
	ll par_ans = ans[par[i]];
	par_ans = (par_ans * ffpow(dp[i], MOD - 2)) % MOD;
	par_ans = (par_ans * ffpow(C(n - 1, cnt[i]), MOD - 2)) % MOD;
	return par_ans;
}

void dfs2(int u, int p=-1) {
	// cout << u << ":\n";
	if (p == -1) {
		ans[0] = dp[0];
	} else {
		ll par_ans = get_parent_ans(u);
		// cout << "par_ans for p=" << p << " = " << par_ans << "\n";
		ans[u] = (dp[u] * par_ans) % MOD;
		ans[u] = (ans[u] * C(n - 1, cnt[u] - 1)) % MOD;
	}
	for(int v: g[u]) {
		if (v != p) {
			dfs2(v, u);
		}
	}
}

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

	pre();
	cin >> n;
	int u, v;
	for(int i = 0 ; i < n - 1 ; i++) {
		cin >> u >> v;
		u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(0);
	dfs2(0);
	for(int i = 0 ; i < n ; i++) {
		cout << ans[i] << "\n";
	}
}


Measured memory_bytes: 21876
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
typedef long long ll;
ll nxt[200100][27];

int main() {
    string s, t;
    cin >> s >> t;
    ll m = s.size();
    s = s + s;
    rep(i, 2 * m + 1) rep(j, 27) nxt[i][j] = -1;
    for(ll i = 2 * m - 1; i >= 0; i--) {
        rep(j, 27) { nxt[i][j] = nxt[i + 1][j]; }
        int c = s[i] - 'a';
        nxt[i][c] = i + 1;
        // cout << "i:" << i << " c:" << (char)(c + 'a') << endl;
    }

    ll now = 0;
    ll res = 0;
    rep(i, t.size()) {
        if(nxt[now][t[i] - 'a'] != -1) {
            ll tmp = now;
            now = nxt[now][t[i] - 'a'];
            res += now - tmp;
            now %= m;
            // cout << t[i] << " " << res << endl;
        } else {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 43008
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
dic = {}
ans = 0
for i in range(N):
    si = input()
    si_list = sorted(si)
    key = ''.join(si_list)
    if key in dic:
        dic[key] = dic[key] + 1
    else:
        dic[key] = 1

for k in dic:
    v = dic[k]
    if v >= 2:
        ans += cmb(v, 2)

print(ans)


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

using namespace std;

int main()
{
    int length;
    string S;
    cin >> length >> S;

    int balance = 0;
    string beginning, ending;

    for(int i = 0; i < S.size(); i++)
    {
        balance += (S[i] == '(' ? 1 : -1);

        if(S[i] == ')' && balance < 0) //Extra
        {
            beginning += '(';
            balance++;
        }
    }

    for(int i = 1; i <= balance; i++)
        ending += ')';

    string answer = beginning + S + ending;
    cout << answer;

    return 0;
}


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

int main(){
  int n; cin >> n;
  int ans = 0;
  for(int i = 0; i < n; i++){
    int a; cin >> a;
    while(a % 2 == 0){
      ans++;
      a /= 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    n--;
    k--;
    int ans = n/k + min(n%k, 1);
    cout << ans <<endl;
    return 0;
}


Measured memory_bytes: 256
/* << IN THE NAME OF GOD >> */
#include <bits/stdc++.h>
using namespace std;



#define err(x) cerr << #x  << " = "<<  x << '\n'
#define out(x) cout << x << '\n'
#define forp(i, r, l) for(int i = int(r); i < int(l); i++)
#define forn(i, r, l) for(int i = int(r); i > int(l); i--)
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll ,ll> pll;
const int maxn = 1e5 + 120;
 


int main(){FAST;
    int a ,b;
    cin >> a >> b;
    cout << max(a + b ,max(a - b ,a * b));

   return 0;
}
 










Measured memory_bytes: 256
/*************************************************************************
  >         File: Main.java
  >       Author: Riho.Yoshioka
  >         Mail: riho.yoshioka@yandex.com
  > Created Time: Sun 21 Aug 2016 08:07:38 PM CST
*************************************************************************/
import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    
    TaskB solver = new TaskB();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskB {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
      int n = in.nextInt();
      int[] a = new int[n + 1];
      long[][] dp = new long[n + 1][2];
      for (int i = 0; i < n; i++) {
        a[i + 1] = in.nextInt();
      }
      for (int i = 0; i <= n; i++) {
        dp[i][0] = dp[i][1] = -1;
      }
      dp[0][0] = 0;
      for (int i = 1; i <= n; i++) {
        if (dp[i - 1][0] >= 0) {
          dp[i][0] = dp[i - 1][0] + a[i] / 2;
          if (a[i] > 0) dp[i][1] = dp[i - 1][0] + (a[i] - 1) / 2;
        }
        if (dp[i - 1][1] >= 0) {
          dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] + a[i] / 2);
          if (a[i] > 0) dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + a[i] / 2);
          if (a[i] > 0) dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] + (a[i] - 1) / 2 + 1);
          if (a[i] > 1) dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + (a[i] - 2) / 2 + 1);
        }
      }
      long ans = Math.max(dp[n][0], dp[n][1]);
      out.println(ans);
    }
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

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

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

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


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


int main() {
    int n, m;
    cin >> n >> m;
    
    int sum = 0;
    for (int i=0; i<m; i++) {
        int a;
        cin >> a;
        sum += a;
    }
    if (n-sum >= 0) {
        cout << n - sum << endl;
    } else {
        cout << -1 << endl;
    }
}

Measured memory_bytes: 3632
N, K = map(int, input().split())
if K > (N-1)*(N-2)//2:
    print(-1)
else:
    s = (N-1)*(N-2)//2
    ans = []
    for i in range(2, N+1):
        ans.append([1, i])
    for i in range(2, N):
        if s == K:
            break
        for j in range(i+1, N+1):
            if s == K:
                break
            ans.append([i, j])
            s -= 1
    print(len(ans))
    for i, j in ans:
        print(i, j)

Measured memory_bytes: 43376
#include<iostream>

using namespace std;

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

int main() {
  int q;
  cin >> q;
  while (q--) {
    int n, res = 0;
    cin >> n;
    while (n >= 10) {
      int mx = 0;
      for (int b = 10; b < n; b *= 10) {
	if (mx < (n / b) * (n % b)) {
	  mx = (n / b) * (n % b);
	}
      }
      n = mx;
      ++res;
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1164
import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)  


Measured memory_bytes: 187932
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-12;

class Compare {
  int monster_x;
  int monster_y;
public:
  Compare(int monster_x,int monster_y)
    : monster_x(monster_x), monster_y(monster_y) {}
  bool operator()(const P& ci,const P& cj) const{
    int dist_i = (ci.first - monster_x) * (ci.first - monster_x)
      + (ci.second - monster_y) * (ci.second - monster_y);
    int dist_j = (cj.first - monster_x) * (cj.first - monster_x)
      + (cj.second - monster_y) * (cj.second - monster_y);
    return dist_i < dist_j;
  }
};

class State{
  int x;
  int y;
  double dist;
};

bool dfs(int hero_x,
         int hero_y,
         double current_time,
         int S,
         int monster_x,
         int monster_y,
         const vector<P>& cristals){
  bool res = false;

  if(S == (1<<cristals.size()) - 1) return true;
  for(int i=0;i<cristals.size();i++){
    if(S & (1<<i)) continue;
    double add_time = sqrt((hero_x - cristals[i].first) * (hero_x - cristals[i].first)
                           + (hero_y - cristals[i].second) * (hero_y - cristals[i].second));
    
    double impurity_arrive_time = sqrt((monster_x - cristals[i].first) * (monster_x - cristals[i].first)
                                       + (monster_y - cristals[i].second) * (monster_y - cristals[i].second));
    if(current_time + add_time >= impurity_arrive_time){
      return false;
    }
    
    res |= dfs(cristals[i].first,cristals[i].second,current_time + add_time,
               S | (1<<i),monster_x,monster_y,cristals);
    if(res) return res;
  }
  return res;
}

int main(){
  int total_cristals;
  int hero_x;
  int hero_y;
  int monster_x;
  int monster_y;
  while(~scanf("%d %d %d %d %d",
               &total_cristals,
               &hero_x,
               &hero_y,
               &monster_x,
               &monster_y)){
    if(total_cristals == 0 && hero_x == 0 && hero_y == 0
       && monster_x == 0 && monster_y == 0) break;
    vector<P> cristals;
    for(int cristal_i = 0; cristal_i < total_cristals; cristal_i++){
      int x,y;
      scanf("%d %d",&x,&y);
      cristals.push_back(P(x,y));
    }
    Compare comp(monster_x,monster_y);
    sort(cristals.begin(),cristals.end(),comp);
    printf("%s\n", dfs(hero_x,hero_y,0,0,monster_x,monster_y,cristals)
           ? "YES" : "NO");
  }
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 10000000000000000
#define endl '\n'
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

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

    int h,w; cin>>h>>w;
    vector<int> cnt(26,0);
    rep(i,h*w){
        char c; cin>>c;
        cnt.at(c-'a')++;
    }

    vector<int> vec(3,0);
    rep(i,26){
        if(cnt.at(i)%4==3){
            vec.at(1)++; vec.at(2)++;
        }else vec.at(cnt.at(i)%4)++;
    }

    if(h%2==0 and w%2==0){
        cout<<(vec.at(0)==26?"Yes":"No")<<endl;
    }else if(h%2==1 and w%2==1){
        if(vec.at(1)==1 and vec.at(2)>=(h/2+w/2)%2 and vec.at(2)<=h/2+w/2)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }else if(h%2==1){
        if(vec.at(1)==0 and vec.at(2)>=(h/2)%2 and vec.at(2)<=w/2)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }else{
        if(vec.at(1)==0 and vec.at(2)>=(w/2)%2 and vec.at(2)<=h/2)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <utility>
#include <math.h>
using namespace std;

int main() {
    int a, b;
    cin >> a;
    vector<int> t(a);
    for (int i = 1; i < a; ++i) {
        cin >> b;
        t[b - 1]++;
    }
    for (int i = 0; i < a; ++i) {
        cout << t[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3996
def main():
    S = input()
    maxlen = 0
    for i in range(len(S)):
        for j in reversed(range(len(S))):
            if i <= j:
                c = 0
                for k in range(i, j+1):
                    if S[k] == "A" or S[k] == "C" or S[k] == "G" or S[k] == "T":
                        c += 1
                    else:
                        break
                if c > maxlen:
                    maxlen = c
    print(maxlen)
main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int  N, D,X,Y,i=0;
    double Z;
    cin>>N>>D;
    while(N--)
    {
        cin>>X>>Y;
        X=abs(X);
        Y=abs(Y);
        Z=pow(X,2)+pow(Y,2);
        Z=pow(Z,0.5);
        if(Z<=D)
        {
            i++;
        }


    }
    cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 4104
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;


int main()
{
    int N;
    cin>>N;
    vector<string> s;
    string t;
    for(int i=0;i<N;i++)
    {
        cin>>t;
        s.push_back(t);
    }

    s.push_back("{{{{{{{{{{");
    for(int i = 0;i<N;i++)
    {
        std::sort(s[i].begin(),s[i].end());
    }
    
    std::sort(s.begin(),s.end());

    long long count=0;
    long long conv=1;
    for(int i = 0;i<N;i++)
    {
        if(s[i]==s[i+1])
        {
            conv++;
        }
        else
        {
            if(conv>=2)
            {
                count+=(conv*(conv-1)/2);
            }
            conv = 1;
        }
        
    }
    cout<<count<<endl;
}

Measured memory_bytes: 7284
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;


int main() {
string S;
cin >> S;
bool ans = true;
if (S.at(0) != 'A') ans = false;
int cnt = 0,a = 0;
for (int i = 2;i < S.size()-1;i++) {
    if (S.at(i) == 'C') {
        cnt++;
        a = i;
    }
}
if (cnt != 1) ans = false;
for (int i = 1;i < S.size();i++) {
    if (i == a) continue;
    if ((int) S.at(i) < 97) ans = false;
}
if (ans == true) cout << "AC" << endl;
else cout << "WA" << endl;

return 0;
}


Measured memory_bytes: 256
//第8回シンデレラガール総選挙は是非本田未央ちゃんに投票をお願いします！
//ファンのことも他のアイドルの子たちのことも本当に大事にしてて、今まで周りに色んなものを与えてくれました。
//今度は私たちが未央ちゃんにお返しをする番です。みんなでガラスの靴を履かせてあげましょう！
// #本田未央を一番星に #本田未央を令和のシンデレラガールに #第8回シンデレラガール総選挙
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
vector<int> gr[200100];
int mx,mxi;
void dfs(int v,int u,int d){
	if(mx<d) mx=d,mxi=v;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(u==w) continue;
		dfs(w,v,d+1);
	}
}
int main()
{
	int n,a,b;cin>>n;
	rep(i,n){
		cin>>a>>b;gr[a].pb(b);gr[b].pb(a);
	}
	mx=mxi=-1;dfs(1,0,0);
	mx=-1;dfs(mxi,0,0);
	if(mx%3==1) cout<<"Second"<<endl;else cout<<"First"<<endl;
}


Measured memory_bytes: 23680
N, M = map(int, input().split())
P = [0] * N

wa = 0
for _ in range(M):
  p, s = input().split()
  index = int(p)-1
  if s == 'WA' and P[index] != -1:
      P[index] += 1
  elif P[index] > -1:
    wa += P[index]
    P[index] = -1
  
print(P.count(-1), wa)

Measured memory_bytes: 3828
import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        int answer = 0;

        while (true) {
            int a = scan.nextInt();
            String op = scan.next();
            int b = scan.nextInt();

            if (op.equals("?")) {
                break;
            }

            if (op.equals("+")) {
                answer = a + b;
            } else if (op.equals("-")) {
                answer = a - b;;
            } else if (op.equals("*")) {
                answer = a * b;
            } else if (op.equals("/")) {
                answer = a / b;
            }
            System.out.println(answer);
        }
    }
}

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

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */

fn main() {
    input! {
        n: u32
    }
    println!("{}", n.pow(2));
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#define N 100
#define INF 2000000000
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int n;
int M[N][N],color[N],d[N],p[N];
   //M??????????????????color????¨??????¶???(0,1,2),d????????????????°???????????¨????
   //p???MST???????°???¨?????¨??????????????????????????????

void Prim() {
	for (int i = 0;i < n;i++) d[i] = INF;
	d[0] = 0;  //?????????????????????????????§???????????§????´???????????????????????????????
	/*p[0] = -1;  //??????????????????????????????????????????*/

	int u;
	while (true) {
		int min = INF;
		for (int i = 0;i < n;i++) {
			if(color[i]!=BLACK&&min>d[i]){
				min = d[i];
				u = i;
			}
		}

	if (min == INF) break;

	color[u] = BLACK;

	for (int v = 0;v < n;v++) 
		if(color[v]!=BLACK&&M[u][v]!=-1)
			if (M[u][v] < d[v]) {
				d[v] = M[u][v];
				/*p[v] = u;*/
				/*color[v] = GRAY;*/
			}

	}

	int sum = 0;
	for (int i = 0;i < n;i++) sum += d[i];
	cout << sum << endl;
		
}

int main() {
	cin >> n;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++) {
			cin >> M[i][j];
			if (M[i][j] == -1) M[i][j] = INF;
		}

	Prim();

}

Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define ll long long

using namespace std;

char ar[700020];
int lefty = 300001;
int righty = 300000;
int heady = 0;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
    string s;
    cin >> s;
    for(int i=0; i < s.length(); i++){
        ++righty;
        ar[righty] = s[i];
    }
    int t,a,b; char ss;
    cin >> t;
    while(t--){
        cin >> a;
        if( a == 1 ){
            heady += 1;
        }
        else{
            cin >> b >> ss;
            if( b == 1 ){
                if(heady%2==0) { ar[lefty-1] = ss; --lefty; }
                else{
                    ar[righty+1] = ss; ++righty;
                }
            }
            else if( b == 2 ){
                if(heady%2==0){ ar[righty+1]=ss; ++righty; }
                else{
                    ar[lefty-1] = ss; --lefty;
                }


            }
        }
    }
    if(heady%2==0){
        for(int i=lefty; i <= righty; i++) cout << ar[i];
    }
    else{
        for(int i=righty; i >= lefty; --i) cout << ar[i];
    }

 }


Measured memory_bytes: 1104
#include<bits/stdc++.h>
using namespace std;
#define TRACE
#define M 1000000007
#define oo 1000000000000000007
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
#define pb push_back
#define M6 1000009
#define M5 500009
#define pi 3.14159265
#define epsilon 1e-6

#ifdef TRACE
    #define trace1(x)                cerr << #x << ": " << x << endl;
    #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
    #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
    #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
    #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
    #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
#else
 
    #define trace1(x)
    #define trace2(x, y)
    #define trace3(x, y, z)
    #define trace4(a, b, c, d)
    #define trace5(a, b, c, d, e)
    #define trace6(a, b, c, d, e, f)
 
#endif
ll power(ll x,ll n,ll m){
    ll res=1;
    while(n>0){
        if(n&1) res=(res*x)%m;
        n/=2;
        x=(x*x)%m;
    }
    return res;
}

ll n,m;
string s,tt;
set<ll> ss[26];
int  main()
{   //ios_base::sync_with_stdio (0), cin.tie (0);
    //sieve();
    //init();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll tc=1,t=0,i,j,k,a,b,c,d,l,r;
    //cin>>tc;
    while(t++<tc){
        //cout<<"Case #"<<t<<": ";
        cin>>s>>tt;
        for(i=0;i<s.size();i++){
            ss[s[i]-97].insert(i+1);
        }
        ll ans=0,q=0,rem=0;
        for(auto u:tt){
            if(ss[u-97].empty()) {ans=-1; break;}
            auto up = ss[u-97].upper_bound(rem);
            if(up==ss[u-97].end()) {
                q++; rem=*ss[u-97].begin();
            }
            else{
                rem=*up;
            }
        }
        if(ans==-1) cout<<"-1";
        else cout<<q*(ll)s.size()+rem;

    }
    return 0;
}

Measured memory_bytes: 5248
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

int n,m;
const int MAX_N = 100;
const int MAX_M = 1000;
const int INF = 100000;
int buf[MAX_N][MAX_N];
int buf2[MAX_N][MAX_N];

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

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      buf[i][j] = INF;
      buf2[i][j] = -1;
    }
  }
  for(int i = 0; i < n; i++){
    buf[i][i] = 0;
    buf2[i][i] = -1;
  }

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


  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < n; k++){
        buf[j][k] = min(buf[j][k], buf[j][i]+buf[i][k]);
      }
    }
  }

  int ret = 0;

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      bool flag = false;
      for(int k = 0; k < n; k++){
        if(buf2[i][j] != -1){
          if(buf[k][i] + buf2[i][j] == buf[k][j]){
            flag = true;
          }
        }
      }
      if(flag){
        ret++;
      }
    }
  }

  cout << m-ret/2 << "\r\n";

  return 0;
}


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

using namespace std;

const int max_n = 3033, mod = 1000000007;

int n, q, a[max_n], dp[max_n][max_n], last[max_n][max_n], ndp[max_n][max_n];
int t, last_updated[max_n][max_n];
int pw[max_n];

int mul(int x, int y) {
    return (1LL * x * y) % mod;
}

int get(int i, int a, int b) {
    if (a == b) {
        return 0;
    }
    return mul(dp[a][b], pw[i - last[a][b]]);
}

void push(int i, int a, int b) {
    if (i < last[a][b]) {
        return;
    }
    dp[a][b] = get(i, a, b);
    last[a][b] = i + 1;
}

void upd(int a, int b) {
    if (a == b) {
        return;
    }
    if (last_updated[a][b] < t) {
        last_updated[a][b] = t;
        dp[a][b] += ndp[a][b];
        if (dp[a][b] >= mod) {
            dp[a][b] -= mod;
        }
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    pw[0] = 1;
    for (int i = 1; i < max_n; ++i) {
        pw[i] = (2 * pw[i - 1]) % mod;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = (a[i] > a[j]);
        }
    }
    for (int i = 0; i < q; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        --x;
        --y;
        for (int j = 0; j < n; ++j) {
            ndp[x][j] = get(i, y, j);
            ndp[y][j] = get(i, x, j);
            ndp[j][x] = get(i, j, y);
            ndp[j][y] = get(i, j, x);
        }
        ndp[x][y] = get(i, y, x);
        ndp[y][x] = get(i, x, y);

        for (int j = 0; j < n; ++j) {
            push(i, x, j);
            push(i, y, j);
            push(i, j, x);
            push(i, j, y);
        }

        ++t;
        for (int j = 0; j < n; ++j) {
            upd(x, j);
            upd(y, j);
            upd(j, x);
            upd(j, y);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ans += get(q, i, j);
            if (ans >= mod) {
                ans -= mod;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 143744
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  string s;
  cin >> s;
  rep(i,sz(s)) {
    cout << s[i];
    if(i == 3) cout << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD     1000000007
#define int     long long int
#define fastIO  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI      3.1415926535897932384626
#define pb      push_back
#define clr(x)  memset(x, 0, sizeof(x))
#define MP      make_pair
const int N=1e5+1;
using namespace std;
int gcd(int a,int b){if(a==0)return b;return gcd(b%a,a);}
int lcm(int a,int b){return (max(a,b)/gcd(a,b))*min(a,b);}
int powermodm(int x,int n,int M){int result=1;while(n>0){if(n % 2 ==1)result=(result * x)%M;x=(x*x)%M;n=n/2;}return result;}
int gcdExtended(int a, int b, int *x, int *y){if (a == 0){*x = 0, *y = 1;return b;}int x1, y1;int gcd = gcdExtended(b % a, a, &x1, &y1);*x = y1 - (b / a) * x1;*y = x1;return gcd;}
int modInverse(int a, int m){int x, y;int g = gcdExtended(a, m, &x, &y);if (g != 1)return -1;else{int res = (x % m + m) % m;return res;}}
bool isPrime(int a){if(a==1) return false;if(a==2) return true;if(a%2==0) return false;int root=sqrt(a);for(int i=3;i<=(int)root;i+=2){if(a%i==0)return false;}return true;}

main()
{
    fastIO;
    int n,w;
    cin >> n >> w;
    int W[n],V[n];
    for(int i=0;i<n;i++)
        cin >> W[i] >> V[i];
    int dp[n+1][w+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(W[i-1]>j)
                dp[i][j]=dp[i-1][j];
            else
            {
                dp[i][j]=max(dp[i-1][j],V[i-1]+dp[i-1][j-W[i-1]]);
            }
        }
    }
    cout << dp[n][w];
}


Measured memory_bytes: 82556
import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

void main() {
    int N; scanf("%d\n", &N);
    auto A = new int[][N];
    foreach (i; 0 .. N) {
        A[i] = readln.chomp.split(" ").map!(to!int).array;
    }
    long Ans = 0;
    foreach (i; 0 .. N) {
        foreach (j; i + 1 .. N) {
            Ans += min(A[i][j], A[j][i]);
        }
    }
    writeln(Ans);
}

Measured memory_bytes: 1524
N = int(input())
H_l = list(map(int, input().split()))

ans = 0
n_jump = 0
height = H_l[0]

for idx in range(1, len(H_l)):
    if H_l[idx] <= height:
        n_jump += 1
    else:
        ans = max(ans,n_jump)
        n_jump = 0
    height = H_l[idx]
        
ans = max(ans,n_jump)
print(ans)

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

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


#define pb push_back
#define ff first
#define ss second
#define INF int(2e9 + 9)
#define BIG_INF ll(9e18)
#define SIZE 2010
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define len(v) int((v).size())
#define BACK(v) ll((v).back())
#define sqr(x) (x) * (x)
#define cube(x) (x) * (x) * (x)
#define filein freopen("input.txt", "r", stdin)
#define fileout freopen("output.txt", "w", stdout);


ll binpow(ll a, ll b, ll MOD = BIG_INF)
{
    ll res = 1;
    a %= MOD;
    while(b)
    {
        if(b & 1)
            res *= a;
        a *= a;
        b >>= 1;
        a %= MOD;
        res %= MOD;
    }

    return res % MOD;
}

const ll mod = 998244353;

int T = 1;
string s;int n;


void _find(int &r, int &l)
{
    r--;
    while(r >= 0 && s[r] == 'W') r--;

    l++;
    while(l < n && s[l] == 'R') l++;
}


void solve()
{

    cin >> n >> s;

    int r = n, l = -1;
    _find(r, l);
    int ans = 0;
    while(l < r)
    {
        swap(s[l], s[r]);
        _find(r, l);
        ans++;
    }
//    cout << s;
    int cntW = 0, cntR = 0;
    for(int i = 1; i < n - 1; i++)
    {
        if(s[i - 1] == 'W' && s[i] == 'R' && s[i + 1] == 'W') cntR++;
        else if(s[i - 1] == 'R' && s[i - 1] == 'W' && s[i - 1] == 'R') cntW++;
    }

    ans += min(cntW, cntR);
    cout << ans;

    return;
}


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

   // filein;fileout;


//    cin >> T;

    while(T--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3768