akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        if(x % 2 == 0) nums.push_back(x);
    }
    int flag = 0;
    for(int i = 0; i < nums.size(); ++i){
        if(nums[i] % 3 == 0 || nums[i] % 5 == 0){
            continue;
        }
        flag = 1;
        break;
    }
    if(flag == 1) cout << "DENIED" << endl;
    else cout << "APPROVED" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int ans[300001];
int cnt[500];
int x[500];
bool check[300001];
P y[500];

int main(){
    cin >> n;
    rep(i,n){
        cin >> x[i];
        y[i].first = x[i];
        y[i].second = i;
    }
    sort(y,y+n);
    for(int i = 1; i <= n*n; i++){
        bool did = false;
        rep(j,n){
            int id = y[j].second, val = y[j].first;
            if(val < i) continue;
            if(val == i){
                if(cnt[id] == id){
                    ans[i] = id;
                    cnt[id]++;
                    did = true;
                    break;
                } else{
                    cout << "No" << endl;
                    return 0;
                }
            } 
            if(cnt[id] < id){
                ans[i] = id;
                cnt[id]++;
                did = true;
                break;
            }
        }
        if(did) continue;
        rep(j,n){
            int id = y[j].second, val = y[j].first;
            if(cnt[id] == n) continue;
            ans[i] = id;
            cnt[id]++;
            break;
        }
    }
    puts("Yes");
    for(int i = 1; i <= n*n; i++){
        if(i != n*n) cout << ans[i]+1 << " ";
        else cout << ans[i]+1 << endl;
    }
}


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

using namespace std;


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

    string n;
    cin >> n;
    for (int i = 0; i < n.size(); ++i) {
        if(n[i] == '7') {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";

}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

using ll = long long;
using namespace std;
ll mod = 1'000'000'007;

const int INF = 1'050'000'000;

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    A += B;
    C += D;
    if (A == C) {
        cout << "Balanced" << endl;
    }
    else if (A < C) {
        cout << "Right" << endl;
    }
    else {
        cout << "Left" << endl;
    }
    return 0;

}

Measured memory_bytes: 256
#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, Q;
    ll ans;
    cin >> N >> M >> Q;
    vector<vector<int>> data(Q, vector<int>(4));
    rep(i, Q){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        data[i] = {a,b,c,d};
    }

    vector<int> array;
    rep(i, M){
        array.push_back(0);
    }
    rep(i, N){
        array.push_back(1);
    }
    
    ans = 0;
    
    do{
        ll sum = 0;
        if(array[0] == 1) continue;
        int curref,temp0Sum;
        curref = 0;
        temp0Sum = 0;
        vector<int> perm(N);
        rep(i, N + M){
            if(array[i] == 1){
                perm[curref] = temp0Sum;
                curref++;
            } else {
                temp0Sum++;
            }
        }
        rep(i, Q){
            if(perm[data[i][1] - 1] - perm[data[i][0] - 1] == data[i][2]){
                sum += (ll)data[i][3];
            }
        }
        ans = max(ans, sum);
        
    }while(next_permutation(array.begin(), array.end()));

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


Measured memory_bytes: 3640
#pragma GCC optimize "trapv"
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define ld long double
#define mp make_pair
#define pii pair<int,int>
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,a,n) for(ll i=a;i<n;i++)
#define all(v) v.begin(),v.end()
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
int main()
{
    fio;
    int t=1;;
    //cin>>t;
    while(t--)
    {
        ll h,w,m;
        cin>>h>>w>>m;
        vector<pair<ll,ll>> c;
        map<pair<ll,ll>,ll> chk;
        rep(i,m)
        {
            ll a,b;
            cin>>a>>b;
            c.pb({a,b});
            pair<ll,ll> p={a,b};
            chk[p]++;
        }
        unordered_map<ll,ll> m1,m2;
        rep(i,m)
        {
            m1[c[i].first]++;
        }
        rep(i,m)
        {
            m2[c[i].second]++;
        }
        ll mx=INT_MIN,f=0,mx1=INT_MIN,s=0;
        for(auto x:m1)
        {
            if(x.second>mx)
            {
                mx=x.second;
                f=x.first;
            }
        }
        for(auto x:m2)
        {
            if(x.second>mx1)
            {
                mx1=x.second;
                s=x.first;
            }
        }
        ll sum=0,mxs=INT_MIN;
        if(mx>=mx1)
        {
            repp(i,1,w+1)
            {
                pair<ll,ll> p={f,i};
                if(chk[p]!=0)
                {
                    sum--;
                }
                sum=sum+(mx+m2[i]);
                mxs=max(mxs,sum);
                sum=0;
            }
            cout<<mxs<<endl;
        }
        else
        {
            repp(i,1,h+1)
            {
                pair<ll,ll> p={i,s};
            if(chk[p]!=0)
                {
                    sum--;
                }
                sum=sum+(mx1+m1[i]);
                mxs=max(mxs,sum);
                sum=0;
            }
            cout<<mxs<<endl;
        }
    }
}

Measured memory_bytes: 72404
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int selectionSort(int *A, int N)
{
    int c = 0;
    REP(i, N)
    {
        int min_j = i;
        FOR(j, i+1, N)
        {
            if (A[j] < A[min_j])
                min_j = j;
        }
        if (i != min_j)
        {
            swap(A[i], A[min_j]);
            c++;
        }
    }
    return c;
}

int main()
{
    int a[100], N;
    cin >> N;
    REP(i, N)
    {
        cin >> a[i];
    }

    int c = selectionSort(a, N);

    REP(i, N)
    {
        cout << a[i];
        if (i != N - 1)
            cout << ' ';
    }

    cout << endl
         << c << endl;
}


Measured memory_bytes: 3084
// Header {{{
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}
// {{{ MaxFlow
class MaxFlow{
    private:
        // destination, capacity, reverse edge index
        const ll inf=1e18;
        struct edge { ll to, cap, rev; };
        ll _n;
        vector<vector<edge>> G;
        vector<bool> used;

        ll dfs (ll src, ll dst, ll flow){
            if (src==dst)
                return flow;
            used[src]=true;
            rep(i,0,G[src].size()){
                edge &e = G[src][i];
                if (!used[e.to] && e.cap > 0) {
                    ll d = dfs(e.to, dst, min(flow, e.cap));
                    if (d>0){
                        e.cap -= d;
                        G[e.to][e.rev].cap += d;
                        return d;
                    }
                }
            }
            return 0;
        }

    public:
        MaxFlow (ll numOfVertex){
            _n = numOfVertex;
            G = vector<vector<edge>>(_n);
        }

        // 0<=src,dst<numOfVertex
        void addEdge(ll src, ll dst, ll cap) {
            G[src].push_back(edge{dst, cap, (ll)G[dst].size()});
            G[dst].push_back(edge{src, 0, (ll)G[src].size()-1});
        }

        ll maxFlow(ll src, ll dst){
            ll flow = 0;
            while(true){
                used = vector<bool>(_n, false);
                ll f = dfs(src, dst, inf);
                if (f==0){
                    return flow;
                }
                flow += f;
            }
        }
};
// }}}

signed main() {
    ll sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;

    // step.1
    rep(i,0, ty-sy) cout<<"U";
    rep(i,0, tx-sx) cout<<"R";

    // step.2
    rep(i,0, ty-sy) cout<<"D";
    rep(i,0, tx-sx) cout<<"L";

    // step.3
    cout<<"L";
    rep(i,0, ty-sy+1) cout<<"U";
    rep(i,0, tx-sx+1) cout<<"R";
    cout<<"D";

    // step.4
    cout<<"R";
    rep(i,0, ty-sy+1) cout<<"D";
    rep(i,0, tx-sx+1) cout<<"L";
    cout<<"U";

    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"
#define MOD 100000009

using namespace std;

typedef long long int lli;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector <int> p(n);
	for(int &x: p) cin >> x;
	int res = 0;
	for(int i=1; i<n-1; i++){
		int mx = max({p[i-1], p[i], p[i+1]});
		int mn = min({p[i-1], p[i], p[i+1]});
		int middle = mx ^ p[i-1] ^ p[i] ^ p[i+1] ^ mn;
		res += (middle == p[i]);
	}	
	cout << res;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include <stdlib.h>



int main(){
 
  char n[5];
  int c,i;
  scanf("%s",n);
  c=0;
  
  for (i=0;i<4;i++){
    if(n[i]=='2')
      c=c+1;}

  
  printf("%d",c);
 
}

Measured memory_bytes: 128
#include<iostream>

using namespace std;

long long a[10], ppl, ans, cnt[10];

int main()
{
	cin >> ppl >> a[1] >> a[2] >> a[3] >> a[4] >> a[5];
	a[0] = ppl;
	cnt[0] = 1;
	for (int i = 1; i <= 5; i++)
	{
		if (a[i] >= a[i - 1])
		{
			cnt[i] = cnt[i - 1];
			a[i] = a[i - 1];
		}
		else
			cnt[i] = (ppl % a[i] == 0? (ppl / a[i]) : (ppl / a[i] + 1));
		ans = max(ans, cnt[i] + i - 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split(" "))
 
a = list(set(map(int, input().split(" "))))
g = a.copy()
 
while not any(x%2 for x in g): g = [i //2 for i in g]
 
if not all(x%2 for x in g): print(0); exit(0)
 
def gcd(a, b):
 
    while b:
 
        a, b = b, a % b
    return a
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
tot = 1
 
for x in a: tot = lcm(tot, x//2)
print((M//tot+1)//2)

Measured memory_bytes: 11356
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define ff first
#define ss second
#define setbits(x)          __builtin_popcountll(x)
#define lp(a,n) for(ll i=a; i<n; i++)
#define lpi(a,n) for(int i=a; i<n; i++)
#define w(t) int t; cin>>t; while(t--)
#define vi vector<int> 
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define inf 1e9
#define LB lower_bound
#define UB upper_bound
const int mod = 1000000007;
using namespace std;
ll gcd(ll a,ll b){
    if(a==0)return b;
    return gcd(b%a,a);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}

int prime[100007];
void SieveOfEratosthenes(int n) 
{ 
    memset(prime, -1, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
         
        if (prime[p] == -1) 
        { 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = p; 
        } 
    } 
    
} 
int lps(string s){
    int len = 0;
    int n = s.length();
    int dp[n];
    dp[0] = 0;
    for(int i=1; i<n; i++){
        if(s[i] == s[len]){
            len++;
            dp[i] = len;
            continue;
        }
        if(len!=0){
            len = dp[len-1];
            i--;
            continue;
        }
        dp[i]=0;
    }
    return dp[n-1];
}
 
ll power(unsigned ll x,unsigned  ll y) 
{ 
    ll res = 1;     
    while (y > 0) 
    { 
        if (y & 1) 
            res = res*x; 
   
        y = y>>1;
        x = x*x;  
    } 
    return res; 
}

//to calculate p1^x  *  p2^x2  *p3^x3 ----------
//i.e. prime factorization and store pi and xi in vector 
vector<pair<ll, ll>> pFactor;

void factorize(long long n) 
{ 
    int count = 0; 
  
    // count the number of times 2 divides  
    while (!(n % 2)) { 
        n >>= 1; // equivalent to n=n/2; 
        count++; 
    } 
  
    // if 2 divides it 
    if (count) 
        pFactor.pb({2,count}); 
  
    // check for all the possible numbers that can  
    // divide it 
    for (long long i = 3; i <= sqrt(n); i += 2) { 
        count = 0; 
        while (n % i == 0) { 
            count++; 
            n = n / i; 
        } 
        if (count) 
            pFactor.pb({i,count});
    } 
  
    // if n at the end is a prime number. 
    if (n > 2) 
        pFactor.pb({n,1}); 
} 



int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
   int a, b, c,k;
   cin>>a>>b>>c>>k;
   int x = 0;
   while(b<=a){
       b*=2;
       x++;
   }
   while(c<=b){
       c*=2;
       x++;
   }
   if(x<=k){
       cout<<"Yes\n";
   }
   else cout<<"No\n";
}

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

void fnInput(int64_t& rnNum)
{
  cin >> rnNum;
}

int fnDigitsCheck(int64_t nDivisor)
{
  int nDigitCnt = 0;
  while (nDivisor)
  {
    nDigitCnt++;
    nDivisor /= 10;
  }

  return nDigitCnt;
}

int fnMultiplCheck(int64_t nNum)
{
  int nMinDigit = fnDigitsCheck(nNum);
                                           // int型 n では n * n が int型の範囲を
  for (int64_t n = 2; n * n <= nNum; n++)  // 超えて桁落ちが発生し TLE となる
  {                                        
    if (nNum % n != 0)  continue;          // nNum の平方根を超えない整数～nNum
    int64_t nOtr = nNum / n;               // で左記検査を行うと TLE となる
    nMinDigit = min(nMinDigit, fnDigitsCheck(nOtr));
  }
  return nMinDigit;
}

int main()
{
  int64_t nNum;
  
  fnInput(nNum);
  cout << fnMultiplCheck(nNum) << endl;

  return 0;
}

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

int main(){
    int n;
    double ans;
    cin >> n;
    if (n % 2 == 1) {
        ans = (n / 2 + 1);
        ans /= n;
    }
    else ans = 0.5;
    cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef vector<ll>vi;
typedef pair<ll,ll>pi;
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
ll max(ll a,ll b){return (a>b?a:b);}
ll min(ll a,ll b){return (a<b?a:b);}
ll gcd(ll a,ll b)
{return (b?gcd(b,a%b):a);
}
void algo()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll sum=0;
    sum+=min(d,a);
    d=d-a;
    if(d>0)
    {
        d=d-b;
        if(d>0)
        {
            sum-=d;
        }
    }
    cout<<sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout<<setprecision(20);
    ll t=1;//cin>>t;
    while(t--)
    {
        algo();
	cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3652
N = int(input())
P = list(map(int, input().split()))
marks = [0]*N
for i in range(N):
  if P[i]==i+1:
    marks[i]=1
b = 0
check = 0
for i in range(1, N):
  if marks[i-1]==1 and marks[i]==1:
    marks[i]=0
print(sum(marks))

Measured memory_bytes: 14008
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll H, W, ans = 0, A, B;

int main()
{
    COMinit();
    cin >> H >> W >> A >> B;
    for (ll i = 1; i <= H - A; i++)
    {
        ans += COM(i + B - 2, B - 1) * COM(W - B + H - i - 1, H - i);
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 12160
import scala.io.StdIn.readLine

object Main {

  def pow(x:Long, y:Long, z:Long):Long = {

    def multi(m:Long, n:Long) = { ( (m%z) * (n%z) ) % z }

    def pow2(m:Long, n:Long, odd:Long, b:Long):Long = {
      n match {
        case 0 => 1
        case 1 => multi(m, odd)
        case _ =>
          pow2(multi(m,m), n/2, (if(n%2==1) multi(odd, b) else odd), multi(b,b))
      }
    }
    pow2(x, y, 1, x)
  }

  def main(args: Array[String]) = {
    val l = readLine().split(" ").map(_.toLong)
    val (m, n) = (l(0), l(1))
    println(pow(m,n,1000000007))
  }
}

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

int main () {
	int N,D,X;
	int ans=0;  
 	cin >> N >> D >> X;

  	int A[N];

  	for (int i = 0; i < N; ++i)
  	{
  		cin >> A[i];
  		ans += (D-1)/A[i] +1;
  	}

  		ans += X;

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

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

template<typename Monoid, typename OperatorMonoid>
struct LazySegmentTree {
    using F = function<Monoid(Monoid, Monoid)>;
    using G = function<Monoid(Monoid, OperatorMonoid)>;
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
    const F f;
    const G g;
    const H h;
    const Monoid M1;
    const OperatorMonoid OM0;
    int sz, height;
    vector<Monoid> data;
    vector<OperatorMonoid> lazy;
    LazySegmentTree(int n, const F f, const G g, const H h,
                    const Monoid &M1, const OperatorMonoid &OM0)
        : f(f), g(g), h(h), M1(M1), OM0(OM0), sz(1), height(0)
    {
        while (sz < n) sz <<= 1, height++;
        data.assign(sz * 2, M1);
        lazy.assign(sz * 2, OM0);
    }
    void set(int k, const Monoid &x) { data[k + sz] = x; }
    void build() {
        for (int k = sz - 1; k > 0; k--) {
            data[k] = f(data[k << 1 | 0], data[k << 1 | 1]);
        }
    }
    inline Monoid reflect(int k) {
        return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
    }
    inline void propagate(int k) {
        if (lazy[k] == OM0) return ;
        lazy[k << 1 | 0] = h(lazy[k << 1 | 0], lazy[k]);
        lazy[k << 1 | 1] = h(lazy[k << 1 | 1], lazy[k]);
        data[k] = reflect(k);
        lazy[k] = OM0;
    }
    inline void thrust(int k) {
        for (int i = height; i > 0; i--) propagate(k >> i);
    }
    inline void recalc(int k) {
        while (k >>= 1) data[k] = f(reflect(k << 1 | 0), reflect(k << 1 | 1));
    }
    void update(int a, int b, const OperatorMonoid &x) {
        thrust(a += sz);
        thrust(b += sz - 1);
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lazy[l] = h(lazy[l], x), ++l;
            if (r & 1) --r, lazy[r] = h(lazy[r], x);
        }
        recalc(a);
        recalc(b);
    }
    Monoid get(int a, int b) {
        thrust(a += sz);
        thrust(b += sz - 1);
        Monoid L = M1, R = M1;
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = f(L, reflect(l++));
            if (r & 1) R = f(reflect(--r), R);
        }
        return f(L, R);
    }
    Monoid operator[](const int &k) { return get(k, k + 1); }
};

const int MAX = numeric_limits<int>::max();
int main() {
    int n, q; cin >> n >> q;
    using T = int;
    using E = int;
    auto f = [](T a, T b) { return T(min(a, b)); };
    auto g = [](T a, E b) { return T(a + b); };
    auto h = [](E a, E b) { return E(a + b); };
    LazySegmentTree<T, E> seg(n, f, g, h, T(MAX), E(0));
    for (int i = 0; i < n; i++) seg.set(i, 0);
    seg.build();
    while (q--) {
        int op; cin >> op;
        int s, t; cin >> s >> t; t++;
        if (op == 0) {
            int x; cin >> x;
            seg.update(s, t, x);
        }
        if (op == 1) {
            cout << seg.get(s, t) << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 4948
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

struct Point {
	int x;
	int y;
};

bool bmap[1000][1000] = { false };
bool smap[1000][1000] = { false };

void add_search(queue<Point>& search, int x, int y, int w, int h)
{
	if (x < 0 || w <= x) return;
	if (y < 0 || h <= y) return;
	if (bmap[x][y]) return;
	if (smap[x][y]) return;

	smap[x][y] = true;
	search.push({ x,y });
}

int main()
{
	int h, w; cin >> h >> w;

	queue<Point> search;
	FOR_LT(y, 0, h) {
		FOR_LT(x, 0, w) {
			char c; cin >> c;
			if (c == '#') {
				bmap[x][y] = true;
				add_search(search, x + 1, y, w, h);
				add_search(search, x - 1, y, w, h);
				add_search(search, x, y + 1, w, h);
				add_search(search, x, y - 1, w, h);
			}

		}
	}

	int count = 0;
	while (!search.empty()) {
		bool has_change = false;
		queue<Point> next_search;

		while (!search.empty()) {
			auto p = search.front();
			search.pop();

			int x = p.x; int y = p.y;
			if (!bmap[p.x][p.y]) {
				bmap[p.x][p.y] = true;
				has_change = true;
			}

			add_search(next_search, x + 1, y, w, h);
			add_search(next_search, x - 1, y, w, h);
			add_search(next_search, x, y + 1, w, h);
			add_search(next_search, x, y - 1, w, h);
		}
		
		search = next_search;
		if (has_change) {
			count++;
		}
	}

	cout << count << endl;

	return 0;
}

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

int main()
{
    int A, B;
    cin >> A >> B;
    string ar_ans[2] = {"Possible", "Impossible"};
    cout << ar_ans[!(A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0)] << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  lli n;
  scanf("%lld", &n);

  lli ans = 0;
  if (n % 2 == 0) {
    lli five  = 10;
    while (n / five != 0) {
      ans += n / five;
      five *= 5;
    }
  }
  printf("%lld\n", ans);
  return 0;
}


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

int main() {
	int A, B, C;
	cin >> A >> B >> C;
	string ans;
	if (C >= A && C <= B) {
		ans = "Yes";
	}
	else {
		ans = "No";
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
using namespace std;
const constexpr int INF = 1e9;
typedef pair<int, int> P;

#define FOR(i, a, n) for (ll i = (ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef vector<int> VI;
const constexpr ll MOD = 1e9 + 7;
const int BITSIZE = 100010;

struct Less {
	bool operator()(const pair<int, int>& x, const pair<int, int>& y) const {
		return x.second < y.second;
	}
};
struct More {
	bool operator()(const pair<int, int>& x, const pair<int, int>& y) const {
		return x.first > y.first;
	}
};
//1-indexed
int bit[100010];

int bit_query(int i) {
	int res = 0;
	for (; i >= 1; i -= i & -i) res = max(res, bit[i]);
	return res;
}

void bit_set(int x, int v) {
	for (; x <= BITSIZE; x += x & -x) {
		bit[x] = max(bit[x], v);
	}
}

ll pow_mod(ll a, ll b){
    ll sum =1;
    while(b>0){
        if(b&1){
            sum *= a%MOD;
        }
        a = a* a%MOD;
        b >>= 1;
    }
    return sum;
}
int main() {
    int N, M, X, Y; cin >> N >> M >> X >> Y;
    
    int maxV=-INF;
    REP(i, N) {
        int a; cin >> a;
        maxV = max(maxV, a);
    }
    int minV=INF;
    REP(i, M){
        int a; cin >> a;
        minV = min(minV, a);
    }
    
    bool ok = false;
    for(int i=maxV+1; i<=minV; ++i){
        if(i>X&&i<=Y) ok = true;
    }
    if(ok) cout << "No War" << endl;
    else cout << "War" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
using namespace std;
using ll = long long;
using ldb = long double;

vector<int> par;

int root(int a) {
	if (par[a] == a)return a;
	else return par[a] = root(par[a]);
}

void unite(int a, int b) {
	int art = root(a), brt = root(b);
	if (art == brt)return;
	par[brt] = art;
}


int main() {
	int N, M; cin >> N >> M;
	par = vector<int>(N + 1);
	for (int i = 1; i <= N; i++) {
		par[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		unite(x, y);
	}

	int ans = 0;
	vector<int> cnt(N + 1);
	for (int i = 1; i <= N; i++) {
		int irt = root(i);
		cnt[irt]++;
		ans = max(ans, cnt[irt]);
	}
	cout << ans << endl;
}


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

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>

typedef long long ll;
typedef unsigned long long ull;

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

const double INF = 1e+09;
const int MOD = 1e9+7;

using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "{ }"; return ostr;}
    ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}
    ostr << "}";
    return ostr;}

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


int main(void){
  ios::sync_with_stdio(false);
  int n;
  int m;
  cin >> n >> m;
  vector<int> a(m);
  REP(i, m){cin >> a[i];}
  int ans = 0;
  REP(i, m){ans += a[i];}
  int res = n - ans;
  if (res < 0) cout << -1 << endl;
  else cout << res << endl;
  return 0;
}



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

bool CheckCanGo(vector<char>& cc, int l, int r) {
  assert(cc[l] != '#');
  assert(cc[r] != '#');
  char prv = '.';
  for (int i = l + 1; i <= r; i++) {
    char ch = cc[i];
    if (ch == '#' && prv == '#') {
      return false;
    }
    prv = ch;
  }
  return true;
}

void Yes() {
  cout << "Yes" << endl;
  exit(0);
}

void No() {
  cout << "No" << endl;
  exit(0);
}

int main() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  a--;
  b--;
  c--;
  d--;
  vector<char> cc(n);

  for (auto& ch : cc) {
    cin >> ch;
  }

  if (!CheckCanGo(cc, a, c) || !CheckCanGo(cc, b, d)) {
    No();
  }

  if (c < b) {
    Yes();
  }

  if (c < d) {
    Yes();
  }
  bool ok = false;
  for (int i = b; i <= d; i++) {
    if (cc[i] == '.' && cc[i - 1] == '.' && cc[i + 1] == '.') {
      ok = true;
    }
  }
  ok ? Yes() : No();
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

int main(){
    int A, B, C; cin >> A >> B >> C;
    int K; cin >> K;
    rep(i, K){
        if(A >= B) B*= 2;
        else C *= 2;
    }
    if(A < B && B < C) cout << "Yes" << endl;
    else cout << "No" << endl;
} 

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

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

using namespace std;

typedef long long ll;

ll cnt[100001];

signed main(){
  int n;
  ll k;
  int a, b;

  cin >> n >> k;
  
  rep(i, n){
    cin >> a >> b;
    cnt[a] += b;
  }

  REP(i, 1, 100001){
    if(k <= cnt[i]){
      cout << i << endl;
      break;
    }
    k -= cnt[i];
  }

}


Measured memory_bytes: 1024
a,b=map(int,input().split())
ans=[["#"]*100 for i in range(50)]
for i in range(50):
    ans.append(["."]*100)

for i in range(0,49,2):
    for j in range(0,100,2):
        if a==1:
            break
        ans[i][j]="."
        a-=1
    if a==1:
        break

for i in range(51,100,2):
    for j in range(0,100,2):
        if b==1:
            break
        ans[i][j]="#"
        b-=1
    if b==1:
        break
print(100,100)
for i in ans:
    print("".join(i))

Measured memory_bytes: 38384
n=int(input())

countAC=0
countWA=0
countTLE=0
countRE=0

for i in range(n):
    s=input()
    if s=="AC":
        countAC += 1
    elif s=="WA":
        countWA += 1
    elif s=="TLE":
        countTLE += 1
    else:
        countRE += 1

print("AC x " + str(countAC))
print("WA x " + str(countWA))
print("TLE x " + str(countTLE))
print("RE x " + str(countRE))

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

typedef long long ll;

const int MAX = 210000;
const int MOD = (int)1e9+7;

ll fac[MAX], finv[MAX], inv[MAX];

// 素因数分解O(√n)
map<int, int> prime_factor(int n){
    map<int, int> res;
    for(int i=2; i*i<=n; i++){
        while(n%i==0){
            ++res[i];
            n /= i;
        }
    }
    if(n!=1) res[n] = 1;
    return res;
}

// テーブルを作る前処理
void comb_init(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i=2; i<MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}

ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main() {
    int N, M;
    comb_init();
    cin >> N >> M;
    auto m = prime_factor(M);
    ll res=1;
    for(auto pa : m){
        //cout << pa.first <<" "<< pa.second << endl;
        int num = pa.second;
        ll tmp = comb(num+N-1, N-1);
        //cout << tmp << endl;
        res = (res*tmp)%MOD;
    }
    
    cout << res << endl;
}


Measured memory_bytes: 5120
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>

using namespace std;

int ab(int n) { if (n > 0) { return n; } else { return -n; } }

int N, ans, t[100001], x[100001], y[100001];

int main() {

	scanf("%d", &N);

	for (int i = 0; i<N; i++) {
		scanf("%d %d %d", &t[i + 1], &x[i + 1], &y[i + 1]);
	}

	t[0] = 0; x[0] = 0; y[0] = 0;

	ans = 1;

	for (int i = 0; i<N; i++) {
		if (ab(x[i + 1] - x[i]) + ab(y[i + 1] - y[i]) > t[i + 1] - t[i] || (x[i + 1] + x[i] + y[i + 1] + y[i] + t[i + 1] + t[i]) % 2 == 1) {
			ans = 0;
		}
	}

	if (ans == 1) { printf("Yes\n"); }
	else { printf("No\n"); }
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Pow(ll x,ll y){
  ll ans = 1;
  while(y){
    if(y%2) ans *= x;
    x *= x;
    y >>= 1;
  }
  return ans;
}
ll to_decimal(string s,ll B){
  int t = s.find("."),i,n = s.size();
  if(t == string::npos) return -1;
  if(s.size()-t-1 > B) return -1;
  ll ans = 0,x = Pow(10,B+t+1-s.size());
  bool minus = s[0] == '-';
  for(i=s.size()-1;i>=minus;i--){
    if(i == t) continue;
    if(s[i] == '-') ans = -ans;
    else ans += (s[i]-'0')*x;
    x *= 10;
  }
  if(minus) ans = -ans;
  return ans;
}
int main(){
  ll x1,y1,x2,y2,x3,y3,x4,y4;int n,i;
  string a,b,c,d,e,f,g,h;
  cin >> n;
  for(i=0;i<n;i++){
    cin >> a >> b >> c >> d >> e >> f >> g >> h;
    x1 = to_decimal(a,5);
    y1 = to_decimal(b,5);
    x2 = to_decimal(c,5);
    y2 = to_decimal(d,5);
    x3 = to_decimal(e,5);
    y3 = to_decimal(f,5);
    x4 = to_decimal(g,5);
    y4 = to_decimal(h,5);
    printf((x2-x1)*(y4-y3) == (x4-x3)*(y2-y1) ? "YES\n":"NO\n");
  }
}


Measured memory_bytes: 3268
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
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++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
 
void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main(){
  ll N,M;
  cin>>N>>M;
  vector<ll> A;
  rep(i,N){
    ll a;
    cin>>a;
    A.push_back(a);
  }
  sort(A.begin(),A.end());
  
  vector<LP> B;
  rep(i,M){
    ll b,c;
    cin>>b>>c;
    B.push_back(make_pair(c,b));
  }
  sort(B.begin(),B.end());
  reverse(B.begin(),B.end());
  
  ll count=0;
  bool ok=true;
  rep(i,M){
    if(!ok) break;
    for(int j=0; j<B[i].second;j++){
      if(A[count]>=B[i].first){
        ok=false;
        break;
      }
      if(count>=N){
        ok=false;
        break;
      }
      A[count]=B[i].first;
      count++;
    }
  }
  
  ll ans;
  rep(i,N){
    ans+=A[i];
  }
  cout<<ans<<endl;
}

    
  
  

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;

ll N;
string s;
vector<pair<string,ll>> v;
ll w[5000][5000];

int main(){
    cin >> N;
    cin >> s;
    for(int i=0;i<N;i++){
        v.push_back(make_pair(s.substr(i,N-i),i));
    }
    sort(v.begin(),v.end());

    //for(int i=0;i<N;i++) cout << v[i].first << endl;

    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            w[i][j] = 0;
        }
    }

    for(int i=0;i<N-1;i++){
        ll m = min(v[i].first.size(),v[i+1].first.size());
        ll l = 0;
        bool f = true;
        for(int j=0;j<m;j++){
            if((v[i].first)[j] != (v[i+1].first)[j]){
                l = j;
                f = false;
                break;
            }
        }
        if(f) l = m;
        w[i][i+1] = l;
    }

    /*
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout << w[i][j] << " ";
        }
        cout << endl;
    }
    */
    for(int i=0;i<N;i++){
        for(int j=i+2;j<N;j++){
            w[i][j] = min(w[i][j-1],w[j-1][j]);
        }
    }
    /*
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout << w[i][j] << " ";
        }
        cout << endl;
    }
    */
    ll max_l = 0;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            w[i][j] = min(w[i][j],abs(v[i].second-v[j].second));
            max_l = max(w[i][j],max_l);
        }
    }
    cout << max_l << endl;
    return 0;
}

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

#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;
const long double PI = (acos(-1));

int main()
{
    long double a, b, x;
    cin >> a >> b >> x;

    if (a * a * b /2.0 >= x) {
        cout << fixed << setprecision(10) << atan(a * b * b / (2 * x)) * 180.0 / PI << endl; 
    } else {
        cout << fixed << setprecision(10) << atan(2 * (a * a * b - x) / (a * a * a)) * 180.0 / PI << endl; 
    }
    return 0;
}



Measured memory_bytes: 384
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(x) cout << fixed << setprecision(x);
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll n; cin >> n; vl num(n); ll sum = 0; ll zerocount = 0; ll mcount = 0;
  rep(i,n){
    ll x; cin >> x; num[i] = abs(x); sum += abs(x);
    if(x < 0) mcount++;
    else if(x == 0) zerocount++;
  }
  
  sort(all(num));
  
  if(zerocount == 0 && mcount % 2 == 1) cout << sum - num[0]*2 << endl;
  else cout << sum << endl;
}
  

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#define FOR(a, b, c, d) for (int a = b; a < c; a += d)
#define ull unsigned long long
#define MOD 1000000007
using namespace std;
 
int main() {
    int w = 0, h = 0;
    cin >> h >> w;
    ull dp[h+1][w+1];
    FOR(i, 0, h+1, 1)
        FOR(j, 0, w+1, 1)
            dp[i][j] = 0;
    dp[0][1] = 1;
    string buf;
    FOR(i, 1, h+1, 1) {
        cin >> buf;
        FOR(j, 1, w+1, 1)
            if (buf[j-1] == '.')
                dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD;
    }
    cout << dp[h][w];
    return 0;
}

Measured memory_bytes: 11408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;
	
	public static void Main(string[] args)
	{
		var p = Console.ReadLine().ToInt();

		Console.WriteLine(p*p);
	}
	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}



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

int main() {
    int N; cin >> N;
    vector<int> A(N), B(N), C(N-1);
    rep(i, N){
        cin >> A[i];
        A[i]--;
    }
    rep(i, N){
        cin >> B[i];
    }
    rep(i, N-1){
        cin >> C[i];
    }

    int ans = 0;
    int befo = -2;

    rep(i, N){
        ans += B[A[i]];
        if(A[i] == befo+1){
            ans += C[befo];
        }
        befo = A[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r();p=map(int,f[2:-1].split())
  if'0'==f[0]:print(g(n,E,*p))
  else:c,d,e=p;E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))


Measured memory_bytes: 6308
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
int n;
void solve(vector<string>& res,int cur,string buf,int num){
  if(cur==n){
    res.push_back(buf);
  }
  else{
    cur++;
    int sup=min(cur,num);
    rep(i,sup){
      string next=buf;
      next+='a'+i;
      if(i>=num-1)solve(res,cur,next,num+1);
      else solve(res,cur,next,num);
    }
  }
}
signed main(){
  cin>>n;
  vector<string> res;
  int cur=0;
  string buf;
  solve(res,cur,buf,1);
  sort(ALL(res));
  int k=res.size();
  rep(i,k){
    cout<<res[i]<<"\n";
  }
  cout<<flush;
  return 0;
}


Measured memory_bytes: 7796
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

// 感覚gを指定した挿入ソート
void insertionSort(int A[], int n, int g){
    for(int i = 0; i < n; i++){
        int v = A[i];
        int j = i - g;
        while(j >= 0 && A[j] > v){
            A[j + g] = A[j];
            j -= g;
            cnt++;
        }
        A[j + g] = v;
    }
}

void  shellSort(int A[], int n){
    // 数列G = {1, 4, 13, 40, 1221, 364, 1093, ...}を生成
    for(int h = 1;;){
        if(h > n) break;
        G.push_back(h);
        h = 3*h + 1;
    }

    for(int i = G.size()-1; i >= 0; i--){
        insertionSort(A, n, G[i]);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &A[i]);
    cnt = 0;

    shellSort(A, n);
    cout << G.size() << endl;
    for(int i = G.size()-1; i >= 0; i--){
        printf("%d", G[i]);
        if(i) printf(" ");
    }

    printf("\n");
    printf("%d\n",cnt);
    for(int i = 0; i < n; i++) printf("%d\n", A[i]);

    return 0;
}


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

void solve() {
    long long N, M, A, s = 0;
    cin >> N >> M;
    map<long long, long long> mp;
    mp[0] = 1;
    rep(i,N) {
        cin >> A;
        s += A;
        s %= M;
        mp[s]++;
    }
    long long ans = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        long long n = itr->second;
        ans += n * (n - 1) / 2;
    }
    cout << ans << endl;
    return;
}

int main() {
    solve();
}


Measured memory_bytes: 4224
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}

template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}

template<typename T> void sort(vector<T>& v) {sort(v.begin(), v.end());}

int main() {
  int64_t h, w, res = numeric_limits<int64_t>::max();
  cin >> h >> w;
  if (h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }
  if (h >= 3) chmin(res, w);
  if (w >= 3) chmin(res, h);
  for (int i = 1; i < h; ++i) {
    int64_t a = i * w;
    int64_t b = (h - i) * (w / 2);
    int64_t c = (h - i) * ((w + 1) / 2);
    chmin(res, max({a, b, c}) - min({a, b, c}));
  }
  for (int i = 1; i < w; ++i) {
    int64_t a = i * h;
    int64_t b = (w - i) * (h / 2);
    int64_t c = (w - i) * ((h + 1) / 2);
    chmin(res, max({a, b, c}) - min({a, b, c}));
  }
  cout << res << endl;
}



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

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

using namespace std;

int main(){
  ll n,x;cin>>n>>x;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(), a.end());
  ll result=0;
  for(auto c :a){
//cout<<c<<' ';
    if(c<=x){
      x-=c;
      result++;
    }else{
      break;
    }
  }

  if(x && result==n)result--;
  cout<<result;

  return 0;
}

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

#define ll long long
#define mod 1000000007
#define pb push_back
#define UM unordered_map

int main()
{
  ll a,b;
  cin>>a>>b;
  ll c[a],sum=0;
  for(ll i=0;i<a;i++)
  {
    cin>>c[i];

  }
  sort(c,c+a);
  if(a<=b)
  cout<<0<<endl;
  else
  {
    for(ll i=0;i<a-b;i++)
    {
      sum+=c[i];

    }
    cout<<sum<<endl;
  }


}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
const int MN=1e5+5;
typedef long long ll;
int main(){
	int n,m,a[MN],b[MN];
	int x,y;
	set<pii>s[MN];
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		s[x].insert(make_pair(y,i));
	}
	for (int i=1;i<=n;i++){
		int cnt=1;
		for(set<pii>::iterator it=s[i].begin();it!=s[i].end();it++){
			a[it->second]=i;b[it->second]=cnt;cnt++;
		}
	}
	for(int i=1;i<=m;i++){
		printf("%06d%06d\n",a[i],b[i]);
	}
	return 0;
}

Measured memory_bytes: 11648
#include <bits/stdc++.h>
#define ll long long
#define MAX 5000005
using namespace std;


int n, cnt[MAX][5];
char s[MAX];

int main()
{
    cin >> n;
    scanf("%s", s+1);
    for(int i = 1; i <= n; i++){
        cnt[i][1] = cnt[i-1][1];
        cnt[i][2] = cnt[i-1][2];
        cnt[i][3] = cnt[i-1][3];
        if(s[i] == 'R') s[i] = 1, cnt[i][1]++;
        else if(s[i] == 'G') s[i] = 2, cnt[i][2]++;
        else s[i] = 3, cnt[i][3]++;
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i+2; j <= n; j++){
            if(s[i] == s[j]) continue;
            char c = 6-s[i]-s[j];
            ans += cnt[j-1][c]-cnt[i][c];
            if(((i+j)%2==0) && s[(i+j)/2] == c) ans--;
        }
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    int avg = (int)round((double)accumulate(arr, arr + n, 0) / (double)n);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        ans +=  (arr[i] - avg) * (arr[i] - avg);
    }
    cout << ans;

    return 0;

}


Measured memory_bytes: 384