akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 2e5 + 10;
int N, K;
LL A[MAX], a_sum[MAX];

LL calc_sum(int l, int r) {
    return (a_sum[r] - a_sum[l] + K) % K;
}

int main(void) {
    cin >> N >> K;
    REP(i, N) {
        cin >> A[i];
        a_sum[i + 1] = (A[i] + a_sum[i] - 1) % K;
    }

    map<LL, LL> cnt;
    LL ans = 0;
    REP(i, N + 1) {
        if (i - K >= 0) {
            cnt[a_sum[i - K]]--;
        }

        ans += cnt[a_sum[i]]++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mod 1000000007
using namespace std;
ll binpow(ll x,ll y)/* (x^y)%p in O(log y) */{ll res=1;while (y > 0){if(y&1)res=(res*x);y = y>>1;x=(x*x);}return res;}
ull binpowmod(ull x,ull y,ull p)/* (x^y)%p in O(log y) */{ull res=1;x=x%p;while (y > 0){if(y&1)res=(res*x)%p;y = y>>1;x=(x*x)%p;}return res;}
ll mod_inverse(ll n,ll p)/* Returns n^(-1) mod p */{return binpowmod(n,p-2,p);}
ull gcd(ull x,ull y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}
bool comp(pair<int,int> x,pair<int,int> y)
{
    if(x.first<y.first)
        return true;
    else if(x.first==y.first)
        return x.second>y.second;
    else
        return false;
}
bool comp_pairs_by_s(pair<ll,ll> &x ,pair<ll,ll> &y)
{
    return x.second<y.second;
}
bool isPowerOfTwo (ll x)  
{  
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));  
}

class cmp      //comparator for priority_queue 
{               //declaration: priority_queue<int,vector<int>,cmp>
public:         
    bool operator()(pair<int,int> A,pair<int,int> B)
    {
        if(abs(A.first-A.second)==abs(B.first-B.second))
            return A.first>B.first;
        return abs(A.first-A.second)<abs(B.first-B.second);
    }
};
// int prime[100005]={0};
// void sieve(void)
// {
//  int i,j;
//  for(i=0;i<100005;i++)
//         prime[i]=1;
//  prime[0]=0,prime[1]=0;
//  for(i=2;i<=sqrt(100005);i++){
//      if(prime[i]){
//          for(j=i*i;j<100005;j+=i){
//              prime[j]=0;
//          }
//      }
//  }
    
// }
void swap(int &x,int &y){
    int temp=x;
    x=y;
    y=temp;
}

void solve()
{   
    ll n,m,sum=0;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        ll x;
        cin>>x;
        sum+=x;

    }
    //cout<<sum;
    if(sum>n)
        cout<<-1;
    else
        cout<<(n-sum);

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


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    int win = 0;
    for (int i = 0; i < n; ++ i) {
        if (i & 1) win += s[i] == 'g';
        else win -= s[i] == 'p';
    }
    cout << win << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cmath>
#include <limits>
#include <numeric>

using namespace std;

uint64_t gcd(uint64_t a, uint64_t b){
	if(b == 0)
		return a;
	return gcd(b,a%b);
}


int main(){
	uint64_t A, B, C, D, E;
	cin >> A >> B >> C >> D;
	E = C*D/gcd(C,D);

	uint64_t res = B - A + 1;
	A -= 1;
	uint64_t tmp1 = (B / C) - (A / C);
	uint64_t tmp2 = (B / D) - (A / D);
	uint64_t tmp3 = (B / E) - (A / E);
	res -= tmp1 + tmp2 - tmp3;
	cout << res << endl;


	return 0;
}



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

int main(){
  int N; cin >> N;
  N %= 10;
  string ans;
  if (N == 3) ans = "bon";
  else if (N == 0 || N == 1 || N ==6 || N == 8) {
    ans = "pon";
  } else {
      ans = "hon";
  }
  cout << ans << endl;
}


Measured memory_bytes: 3532
N = int(input())
dic = {'M':0,'A':0,'R':0,'C':0,'H':0}
for _ in range(N):
    tmp = input()[0]
    if tmp in dic:
        dic[tmp] += 1
print(dic['M']*dic['A']*dic['R']+
dic['M']*dic['A']*dic['C']+
dic['M']*dic['A']*dic['H']+
dic['M']*dic['C']*dic['R']+
dic['M']*dic['H']*dic['R']+
dic['M']*dic['C']*dic['H']+
dic['C']*dic['A']*dic['R']+
dic['H']*dic['A']*dic['R']+
dic['C']*dic['H']*dic['R']+
dic['C']*dic['A']*dic['H'])

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
using ll=long long int;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &e: a) cin >> e;

    vector<int> ans(n, 0);

    for (int i = n-1; i >= 0; --i) {
        int acc = 0;
        for (int j = i+i+1; j < n; j += i+1) {
            acc += ans[j];
        }
        ans[i] = (acc&1)^a[i];
    }

    int m = count(ans.begin(), ans.end(), 1);
    cout << m << endl;
    for (int i = 0; i < n; ++i) {
        if (ans[i]) cout << i+1 << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 2432
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

match = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [0]+[-float('inf')]*N

for i in range(1, N+1):
    dp[i] = max([10*dp[max(-1,i-match[a])] + a for a in A])

print(''.join(sorted(str(dp[-1]), reverse = True)))


Measured memory_bytes: 14964
#include <stdio.h>

#define BAGGAGE 131072
#define TRACK 131072

int checkP(int n, int k, int w[], int P) {
  int i, j, W[TRACK]= {0};

  //  puts("");
  j = 1;
  for (i = 0; i < n; i++) {
    if ((W[j] + w[i]) <= P) {
      W[j] += w[i];
      //  printf("W[%d]:%d\n", j, W[j]);
    }
    else {
      i--;
      j++;
      //      printf("over! j->%d\n", j);
      if (k < j) {
	//	printf("j over P! recursive\n");
	return checkP(n, k, w, P + 1);
      }
    }
  }
  //  printf("%d\n", P);
  return P;
}


int main(void) {
  int i, n, k, w[BAGGAGE] = {0}, P;
  double W = 0;
  
  scanf("%d %d", &n, &k);
  for (i = 0; i < n; i++) {
    scanf("%d", &w[i]);
    W += w[i];
  }
  // calculate average and round up
  P = (int)(W / k + 0.9);
  for (i = 0; i < n; i++) {
    if (P < w[i])
      P = w[i];
  }

  P = checkP(n, k, w, P);
  printf("%d\n", P);

  return 0;
}

Measured memory_bytes: 1628
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace ABC127
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int r = int.Parse(s[0]);
            int D = int.Parse(s[1]);
            int x = int.Parse(s[2]);
            
            for (int i = 0; i < 10; i++)
            {
                x =  r * x - D;
                Console.WriteLine(x);
            }
        }
    }
}

Measured memory_bytes: 13140
#pragma comment(linker, "/stack:336777216")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef long double ld;
typedef unsigned long long ull;
#define X first
#define Y second
#define mp make_pair
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class X> using indexed_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int M = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int modpow(int n, int k, int MOD);

/**************** code starts here ****************/

void poppingfever() {
	int k, a, b; cin >> k >> a >> b;
	if (k+1 <= a) {
		cout << k+1; return;
	}

	int bis = a;
	k -= bis - 1;

	int profitper2 = max(2LL, b-a);
	int turn = k/2;
	k %= 2;

	bis += k;

	bis += profitper2*turn;

	cout << bis;
}

/**************************************************/

signed main() {
	#ifdef fastfurioustransform
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
 
	ios::sync_with_stdio(0); cin.tie(0);
	//cout << fixed << setprecision(12);
 
	int t = 1; //cin >> t;
	for (int i = 1; i <= t; i++) {
		poppingfever();
	}
 
	return 0;
}

int modpow(int n, int k, int MOD) {
	int ans = 1; n %= MOD;
	while (k > 0) {
		if (k & 1) ans = (ans*n) % MOD;
		k >>= 1; n = (n*n) % MOD;
	}
	return ans;
}

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

// parity
int main() {
    int N; cin >> N;
    vector<int> t(N+1), x(N+1), y(N+1);
    rep(i, N) {
        cin >> t[i+1] >> x[i+1] >> y[i+1];
    }
    bool can = true;
    rep(i, N) {
        int dt = t[i+1] - t[i];
        int dist = abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);
        if (dt < dist) can = false;
        if (dist % 2 != dt % 2) can = false;
    }
    if (can) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

#define inf 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector <ull> vu;
typedef vector <vector <int>> vvi;
typedef pair <int, int> pi;
typedef vector <pair <int, int>> vpi;

int n;

vl v;

ll sum = 0;
int prevX;

void read() {
  cin >> n;
  v.pb(0);
  for(int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    v.pb(x);
    sum += abs(x - prevX);
    prevX = x;
  }
  v.pb(0);
  sum += abs(prevX);
}

void solve() {
  for(int i = 1; i <= n; ++i) {
    ll nr = abs(v[i] - v[i - 1]) + abs(v[i + 1] - v[i]);
    cout << sum - nr + abs(v[i - 1] - v[i + 1]) << "\n";
  }
}


int main() {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  //cin >> t;           // PLEASE REMOVE IT IF NEEDED
  while(t) {
    --t;
    read();
    solve();
  }
  return 0;
}


Measured memory_bytes: 2164
#include <bits/stdc++.h>
#define int long long
#define ALL(obj) (obj).begin(), (obj).end()
#define fi first
#define se second
#define NIL -1
using ll = long long;
const ll MOD = 1000000007;
#define REP(i,n) for (ll i=0; i < (n); ++i)
#define FOR(i,a,b) for (ll i=(a); i < (b); ++i)
using namespace std;

int get_gcd(int a, int b){while(1){if (a < b) swap(a, b); if (b == 0) return a; a %= b;}}
int get_lcm(int a, int b){return a * b / get_gcd(a, b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

  int x,y,z,k;
  cin >> x >> y >> z >> k;
  vector<int> a(x),b(y),c(z);
  REP(i,x) cin >> a[i];
  REP(i,y) cin >> b[i];
  REP(i,z) cin >> c[i];
  sort(ALL(a), greater<int>());
  sort(ALL(b), greater<int>());
  sort(ALL(c), greater<int>());

  struct Triplet {
    int l,m,n;
  };
  auto sum = [&](const Triplet& s) {
    return a[s.l]+b[s.m]+c[s.n];
  };
  auto cmp_pq = [&](const Triplet& s, const Triplet& t) {
    return sum(s) < sum(t);
  };
  priority_queue<Triplet, vector<Triplet>, decltype(cmp_pq)> pq(cmp_pq);
  auto cmp_set = [](const Triplet& s, const Triplet& t) {
    if (s.l != t.l) return s.l < t.l;
    else if (s.m != t.m) return s.m < t.m;
    else return s.n < t.n;
  };
  set<Triplet, decltype(cmp_set)> used(cmp_set);

  pq.push(Triplet{0,0,0});
  used.insert(pq.top());
  REP(i,k) {
    const Triplet t = pq.top(); pq.pop();
    cout << sum(t) << endl;

    Triplet next;

    next = Triplet{t.l+1, t.m, t.n};
    if (next.l < x && used.find(next) == used.end()) {
      pq.push(next);
      used.insert(next);
    }

    next = Triplet{t.l, t.m+1, t.n};
    if (next.m < y && used.find(next) == used.end()) {
      pq.push(next);
      used.insert(next);
    }

    next = Triplet{t.l, t.m, t.n+1};
    if (next.n < z && used.find(next) == used.end()) {
      pq.push(next);
      used.insert(next);
    }
  }

  return 0;
}


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

typedef vector<vector<int> > Graph;
typedef pair<int, int> pii;
struct Node{
  int ord, low;
};

class BridgeFind{
public:
  BridgeFind(Graph _g){
    g = _g;
    node.resize(g.size(), Node{-1, (int)1e9});
  }
  vector<pii> find(){
    if(v_ord == 0)dfs();
    return bridge;
  }
private:
  void dfs(int v  = 0,
           int previous = -1){
    node[v].ord = node[v].low = v_ord++;
    int to;
    for (int i = 0; i < g[v].size(); i++) {
      to = g[v][i];
      if(previous == to)continue;
      if(node[to].ord == -1) dfs(to, v);
      node[v].low = min(node[v].low, node[to].low);
    }
    if(node[v].low == node[v].ord and previous != -1){
      if(previous > v)bridge.emplace_back(pii(v, previous)); 
      else bridge.emplace_back(pii(previous, v));      
    }

  }
  int v_ord = 0;
  vector<pii> bridge;
  Graph g;
  vector<Node> node;
};

int main(int argc, char *argv[]){
  int n, m;
  std::cin >> n >> m;
  Graph g(n, vector<int>());
  for (int i = 0; i < m; i++) {
    int to, from;
    std::cin >> to >> from;
    g[to].push_back(from);
    g[from].push_back(to);
  }
  BridgeFind bf(g);
  vector<pii> bridge = bf.find();
  sort(bridge.begin(), bridge.end());
  for (int i = 0; i < bridge.size(); i++) {
    std::cout << bridge[i].first << " " << bridge[i].second << std::endl;
  }
  // for (auto i: bridge){
  //   std::cout << i.first << " " << i.second << std::endl;
  // }
  return 0;
}

Measured memory_bytes: 5472
#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

typedef long long ll;

int f[200005];

int solve(int n,int up) {
  int s=0;
  for(int i=1;i<=n;i++) {
  	if (i>up+1) s=(s-f[i-up-1]+MOD)%MOD;
  	f[i]=(s+((i<=up)?i:0))%MOD;
  	s=(s+f[i])%MOD;
  }
  return f[n];
}

int solve2(int n) {
  f[1]=1;
  for(int i=2;i<=n+1;i++) f[i]=(f[i-1]+f[i-2])%MOD;
  return (f[n+1]+f[n-1])%MOD;
}

char str[200005];

int main() {
  int n,m;
  scanf("%d%d%s",&n,&m,str+1);
  if (str[1]=='B') {
  	for(int i=1;i<=m;i++) str[i]=((str[i]=='R')?'B':'R');
  }
  bool v=0;
  for(int i=1;i<=m;i++)
    if (str[i]=='B') {
    	v=1;
    	break;
	}
  if (!v) {
  	printf("%d\n",solve2(n));
  	return 0;
  }
  if (n&1) {
  	puts("0");
  	return 0;
  }
  int minn=n,s=0;
  bool fir=1;
  for(int i=1;i<=m;i++)
    if (str[i]=='R') s++;
    else {
    	if (s&&(fir||(s&1))) minn=min(minn,s);
    	s=fir=0;
	}
  printf("%d\n",2*solve(n>>1,(minn>>1)+1)%MOD);
  return 0;
}

Measured memory_bytes: 1280
//Abhinav ---IIIT_A
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define f(i,x,n) for(int i=x;i<(int)n;++i)
#define vpii vector<pair<int,int>>
#define vi vector<int>
#define mpii map<pair<int,int>,int>
#define mpivpii map<int,vector<pair<int,int>>>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define mpi map<int,int>
#define vvi vector<vector<int>>
#define vvvi vector<vvi>
ld pie=3.141592653589;
int mod=1e9+7;

bool Compare(pair<int,int> a, pair<int,int> b)
{
    int l1=a.ss-a.ff+1;
    int l2=b.ss-b.ff+1;
    if(l1!=l2) return l1>l2;
    return a.ff > b.ff;
}
std::priority_queue<pii, std::vector<pii>, std::function<bool(pii, pii)>> pq(Compare);


void solve(){
  int n,k; cin>>n>>k;
  int p[n]; f(i,0,n){
    cin>>p[i]; --p[i];
  }
   int copy=k;
  int c[n]; f(i,0,n) cin>>c[i];
  int ans=LLONG_MIN;
  f(i,0,n){
    int bg=p[i];
    vi ret;
    while(bg!=i){
      ret.pb(c[bg]);
      bg=p[bg];
    }
    ret.pb(c[i]);
    int cs=0;
    for(auto it : ret) cs+=it;
    int curr=ret[0];
    int mps=curr;
    int mpp=1;
    for(int i=1;i<ret.size();++i){
      curr+=ret[i];
      if(mps<curr){
        mps=curr;
        mpp=i+1;
      }
    }
    int tpp=0;
    int len=ret.size();
    if(k>len){
      if(cs >= 0){
        tpp+=cs*(k/len);
        k=k-(k/len)*len;
        int add=0; curr=0;
        for(int j=0;j<k;++j){
          curr+=ret[j];
          add=max(add,curr);
        }
        int xx=LLONG_MAX;
        curr=0;
        for(int j=len-1;j>=0;--j){
         curr+=ret[j];
         xx=min(curr,xx);
        }
        if(xx>0) xx=0;
        tpp+=max(add,abs(xx));
      }else{
        tpp+=mps;
      }
    }else{
        int add=ret[0]; curr=ret[0];
        for(int j=1;j<k;++j){
          curr+=ret[j];
          add=max(add,curr);
        }
        tpp+=add;
    }
    k=copy;
   ans=max(ans,tpp);
  }
  cout<<ans<<"\n";
}


int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);
  int t=1; //cin>>t;
  while(t--) solve();
  return 0;
}
// check for overflows dummy !!!


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

int main(){
  int N; cin >> N;
  vector<int> A(N);
  vector<int64_t> B(N);
  for(int i=0;i<N;i++){
    cin >> A[i];
    B[A[i]-1]++;
  }
  int64_t rans=0;
  for(int i=0;i<N;i++){
    rans+=(B[i]-1)*B[i]/2;
  }
  for(int i=0;i<N;i++){
    cout << rans-B[A[i]-1]+1 << endl;
  }
  return 0;
}
    
  
    

Measured memory_bytes: 4992
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    LL n,a,b;
    cin >> n >> a >> b;
    VLL x(n);
    REP(i,0,n) cin >> x[i];
    /*
    LL mdiff = 0;
    REP(i,1,n) mdiff = max(mdiff, x[i] - x[i-1]);
    LL sub = max(mdiff,b);
    */
    LL ans = 0;
    REP(i,1,n) ans += min(b, (x[i] - x[i-1]) * a);
    cout << ans << endl;
}

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;


int main()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	vector<int> v1(v);
	sort(v1.begin(), v1.end());

	auto show = [&]()
	{
		for (int i = 0; i < n; i++)
		{
			string s = (i == n - 1) ? "\n" : " ";
			cout << v[i] << s;
		}
	};

	for (int i = 1; i < n; i++)
	{
		show();
		if (v == v1)
		{
			return 0;
		}
		if (v[i - 1] < v[i])
		{
			continue;
		}
		//int temp = v[i];
		for (int j = i; j > 0; j--)
		{
			if (v[j - 1] > v[j])
			{
				swap(v[j - 1], v[j]);
			}
		}
	}
	show();
	return 0;
}

Measured memory_bytes: 3132
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int asc(const void* a, const void* b) {
	return *(int*)a- *(int*)b;
}

int main()
{
	int n, p[55];
	int cnt = 0;
	cin >> n;
	rep(i, n) cin >> p[i];
	for (int i = 0; i < n; i++) {
		if (p[i] != i + 1) {
			cnt++;
		}
	}
	if (cnt > 2) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
}

Measured memory_bytes: 256
import numpy as np

N, L = map(int, input().split())

aji_sum = 1 / 2 * N * (N + 2*L - 1)
aji_arr = np.ones(N) * L
aji_arr += np.arange(N)

eat_a = aji_arr[np.argmin(np.abs(aji_arr))]
    
print(int(aji_sum - eat_a))

Measured memory_bytes: 20640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define MAX(a, b, c) max(max(a, b), c)
using namespace std;

int main(){
  int n;
  scanf("%d", &n);
  pair<pair<string, int>, int> sp[110];
  REP(i,n){
    int p;
    char c[15];
    scanf("%s%d",&c,&p);
    string s=c;
    sp[i] = make_pair(make_pair(s, -p), i+1);
  }
  sort(sp,sp+n);
  REP(i,n) cout << sp[i].second << endl; 
 
}


Measured memory_bytes: 256
#include <stdio.h>
#include <queue>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, h, w, n, r, c, now;
  scanf("%lld%lld%lld%lld%lld", &h, &w, &n, &r, &c);
  char s[n + 10], t[n + 10], d[5] = "RLDU", dr[5] ="LRUD";
  ll f[4] = {w + 1 - c, c, h + 1 - r, r}, fr[4] = {c, w + 1 - c, r, h + 1 - r};
  bool flg[n];
  for(i = 0; i < n; ++i) flg[i] = false;
  scanf("%s%s", s, t);
  for(i = 0; i < 4; ++i) {
    priority_queue<ll> q;
    now = f[i];
    for(j = 0; j < n; ++j) {
      if(s[j] == d[i]) now--;
      if(!now) {
        if(q.empty()) {
          printf("NO");
          return 0;
        }
        flg[q.top()] = true;
        q.pop();
        now++;
      }
      if(t[j] == dr[i]) q.push(j);
    }
    now = fr[i];
    for(j = 0; j < n; ++j) {
      if(s[j] == d[i]) now++;
      if(t[j] == dr[i] && flg[j]) now--;
      if(!now) {
        printf("NO");
        return 0;
      }
    }
  }
  printf("YES");
  return 0;
}

Measured memory_bytes: 1912
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final Scanner sc    = new Scanner(System.in);
    static final int     MOD   = (int) 1E9 + 7;
    static final long    INF_L = (long) 4E18;

    public static void main(String[] args) {
        int X = nint();
        int Y = nint();
        int ans = 0;
        switch (X) {
        case 3: ans += 100000; break;
        case 2: ans += 200000; break;
        case 1: ans += 300000; break;
        default: break;
        }
        switch (Y) {
        case 3: ans += 100000; break;
        case 2: ans += 200000; break;
        case 1: ans += 300000; break;
        default: break;
        }
        if (X == 1 && Y == 1) {
            ans += 400000;
        }
        System.out.println(ans);
    }

    @Deprecated
    static int nint() {
        return sc.nextInt();
    }

    @Deprecated
    static int[] nints(int N) {
        return nints(0, N, 0);
    }

    @Deprecated
    private static int[] nints(int padL, int N, int padR) {
        int[] a = new int[padL + N + padR];
        for (int i = 0; i < N; i++)
            a[padL + i] = nint();
        return a;
    }

    static long nlong() {
        return sc.nextLong();
    }

    static long[] nlongs(int N) {
        return nlongs(0, N, 0);
    }

    static long[] nlongs(int padL, int N, int padR) {
        long[] a = new long[padL + N + padR];
        for (int i = 0; i < N; i++)
            a[padL + i] = nlong();
        return a;
    }

    static double ndouble() {
        return sc.nextDouble();
    }

    static double[] ndoubles(int N) {
        return ndoubles(0, N, 0);
    }

    static double[] ndoubles(int padL, int N, int padR) {
        double[] d = new double[N + padL + padR];
        for (int i = 0; i < N; i++) {
            d[padL + i] = ndouble();
        }
        return d;
    }

    static String nstr() {
        return sc.next();
    }

    static char[] nchars() {
        return sc.next().toCharArray();
    }

    static char[] nchars(int padL, int padR) {
        char[] temp = sc.next().toCharArray();
        char[] ret = new char[temp.length + padL + padR];
        System.arraycopy(temp, 0, ret, padL, temp.length);
        return ret;
    }

    static char[][] nchars2(int H, int W) {
        return nchars2(H, W, 0, 0);
    }

    static char[][] nchars2(int H, int W, int padLU, int padRD) {
        char[][] a2 = new char[H + padLU + padRD][W + padLU + padRD];
        for (int i = 0; i < H; i++)
            System.arraycopy(nchars(), 0, a2[padLU + i], padLU, W);
        return a2;
    }

    static long min(long... ls) {
        return Arrays.stream(ls).min().getAsLong();
    }

    static long max(long... ls) {
        return Arrays.stream(ls).max().getAsLong();
    }

    static long abs(long a) {
        return Math.abs(a);
    }
}


Measured memory_bytes: 24020
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define deb(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;


void Main(){

  int A,B;
  cin>>A>>B;

  cout << (A+B)%24 <<"\n";

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


Measured memory_bytes: 256
def solve(N, As):
    colors = set()
    allcount = 0
    for a in As:
        a -= a % 400
        n = a // 400
        if n < 8:
            colors.add(n)
        else:
            allcount += 1
    return max(len(colors), 1), len(colors) + allcount


if __name__ == "__main__":
    N = int(input())
    As = map(int, input().split(" "))
    m1, m2 = solve(N, As)
    print(m1, m2)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		int x = -1;
		int y = -1;

		int[] groupA = {1, 3, 5, 7, 8, 10, 12};
		int[] groupB = {4, 6, 9, 11};

		if(a == 2) {
			x = 2;
		}
		if(b == 2) {
			y = 2;
		}

		for(int i = 0; i < groupA.length; i++) {
			if(groupA[i] == a) {
				x = 0;
			}
			if(groupA[i] == b) {
				y = 0;
			}
		}

		for(int i = 0; i < groupB.length; i++) {
			if(groupB[i] == a) {
				x = 1;
			}
			if(groupB[i] == b) {
				y = 1;
			}
		}

		if(x == y && x != -1 && y != -1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n;
pair < int , int > res1,res2,res3;	
main (){
	cin>>n;
	
	res1.F=res2.F=res3.F=2e9;
	
	for (int i=1; i<=n; i++) {
		int x;
		cin>>x;
		if (x<res1.F) res3=res2,res2=res1,res1.F=x,res1.S=1;
			else
		if (x==res1.F) res1.S++;	
			else
		if (x<res2.F) res3=res2,res2.F=x,res2.S=1;
			else
		if (x==res2.F) res2.S++;
			else
		if (x<res3.F) res3.F=x,res3.S=1;
			else
		if (x==res3.F) res3.S++;
	}
	
	if (res1.S==n && res1.F==0) {
		cout<<"Yes\n";
		return 0;
	}
	
	if (n%3!=0) {
		cout<<"No\n";
		return 0;
	}
	
	if (!res1.F) {
		if (res1.S==n/3 && res2.S==(n/3)*2) cout<<"Yes\n";
									   else cout<<"No\n";
		return 0;
	}
	
	if (res1.S==n/3 && res2.S==(n/3) && res3.S==(n/3) && (res1.F^res2.F)==res3.F) cout<<"Yes\n";
		else cout<<"No\n";
}

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

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

	string ans = "";
	rep(i, 0, s.size()) if ((i) % 2 == 0) ans += s[i];

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
#include<iostream>
  
int main() {
  int N, M; std::cin >> N >> M;
  int a=1, b=N;
  for(int i = 0; i < M; ++i) {
    std::cout << a << " " << b << "\n";
    ++a; --b;
    int d1 = b-a, d2 = N-d1;
    if(d1 == d2 || d1+2 == d2) --b;
  }
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >>n;
  vector<int> vec(n);
  vector<int> vec2(n);
  for(int i=0;i<n;i++){
    vec2[i]=0;
  }
  for(int i=0;i<n;i++){
    cin >>vec[i];
  }
  int i=0;
    while(i<n){
    int j=i;
    while(vec[j]>=vec[j+1]&&j<n-1){
      vec2[i]++;
      j++;
    }
      i=j+1;
  }
  sort(vec2.begin(),vec2.end());
  cout <<vec2[n-1]<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int n;
int total = 0;
int t[300] = {0};
int vs[300] = {0};

double f(double l, double r, double v, double x) {
	if(x < l) return v + l - x;
	if(l <= x && x <= r) return v;
	return v + x - r;
}

double vel(double x) {
	double minv = f(0, 0, 0, x);
	double new = f(total, total, 0, x);
	minv = minv < new ? minv : new;
	int i;
	double l = 0, r = 0;
	for(i=0;i<n;i++) {
		r += t[i];
		new = f(l, r, vs[i], x);
		minv = minv < new ? minv : new;
		l = r;
	}
	return minv;
}

int main() {
	scanf("%d", &n);
	int i;
	for(i=0;i<n;i++) {
		scanf("%d", &t[i]);
		total += t[i];
	}
	for(i=0;i<n;i++) {
		scanf("%d", &vs[i]);
	}
	double area = 0;
	for(i=0;i<total;i++) {
		area += 0.25 * (vel(i) + 2 * vel(i+0.5) + vel(i+1));
	}
	printf("%f\n", area);
	return 0;
}

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


int main() {
	int a,b;
    
    cin >> a >> b;

    if (a > 2*b){
        cout << a-2*b << endl;
    }else{
        cout << 0 << endl;
    }

	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
 
int main(void) {
	int a,b,c,w,h;
    scanf("%d %d %d %d %d",&w,&h,&a,&b,&c);
    if(0>a-c){
    	printf("No\n");
    }else if(0>b-c){
    	printf("No\n");
    }else if(w<a+c){
    	printf("No\n");
    }else if(h<b+c){
    	printf("No\n");
    }else{
    	printf("Yes\n");
    }
	return 0;
}


Measured memory_bytes: 2112
#include <map>
#include <list>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a,b,sum;
int check(int n)  
{  
    int p;  
    p=n;    
    int k=0;   
    while(p!=0)   
    {  
        k=k*10+p%10;  
        p=p/10;  
    }  
    if(k==n)   
        return true;  
    else  
        return false;  
}
int main()
{
	cin>>a>>b;
	for (int i=a;i<=b;i++)
	{
		if (check(i))
		   sum++;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a,b,c,d,e,f;
	scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);
	a*=100;
	b*=100;
	int i,j,k,l;
	int w,s,answ,anss;
	answ=anss=0;
	for(i=0;i<=f;i+=a)
	{
		for(j=0;i+j<=f;j+=b)
		{
			for(k=0;i+j+k<=f;k+=c)
			{
				for(l=0;i+j+k+l<=f;l+=d)
				{
					w=i+j;
					s=k+l;
					if(w*e>=100*s)
					{
						if(anss*(w+s)<=s*(answ+anss))
						{
							answ=w;
							anss=s;
						}
					}
				}
			}
		}
	}
	printf("%d %d\n",answ+anss,anss);
	return 0;
}

Measured memory_bytes: 128
import java.io.IOException;
import java.util.Scanner;
class Main{
	public static void main(String[] args)throws NumberFormatException, IOException{
		//System.out.print(" ");
		Scanner scan = new Scanner(System.in);
		String ring =scan.nextLine();
		String kadai =scan.nextLine();
		char[] moji = ring.toCharArray();
		int kadainagasa = kadai.length();
		String hikaku = "";
		int hikakunagasa = ring.length();
		int kai = 0;
		for(int i=0; i<hikakunagasa; i++){
				hikaku = "";
				kai = 0;
				for(int ii=0; ii<kadainagasa; ii++){
					int i2 = ii;
					if(i + i2 >= hikakunagasa){
						i2 -= hikakunagasa;
					}
					hikaku = hikaku + moji[i+i2];
				}
//				System.out.println(hikaku);
				if(kadai.equals(hikaku)){
					System.out.println("Yes");
					kai = 1;
					break;
				}
		}
		if(kai == 0){
			System.out.println("No");
		}
	}
}

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

int main() {
  int N, tmp1, tmp2, pow;
  
  cin >> N;
  tmp1 = 0;
  tmp2 = N;
  pow = 100000000;
  
  for (int i = 8; i > 0; i--) {
    if (tmp2 / pow < 10) {
      tmp1 += (tmp2 / pow);
      tmp2 = tmp2 % pow;
    }
    pow /= 10;
  }
  tmp1 += tmp2;
  
  if (N % tmp1 == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


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

#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 1e5 + 5, LN = 17, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

ll n, s;

void check(ll b) {
    if (b < 2) return;
    ll sum = 0;
    ll temp = n;
    while (temp) {
        sum += temp % b;
        temp /= b;
    }
    if (sum == s) {
        cout << b << '\n';
        exit(0);
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> s;
    for (ll i = 2; i * i <= n + n; i++) {
        check(i);
    }
    vector<ll> bases;
    ll dif = n - s;
    for (ll i = 1; i * i <= dif; i++) {
        if (dif % i == 0) {
            bases.push_back(i);
            bases.push_back(dif / i);
        }
    }
    sort(all(bases));
    for (ll i : bases) check(i + 1);
    check(n);
    check(n + 1);
    cout << -1 << '\n';
    return 0;
}


Measured memory_bytes: 384
#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 long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = mod * mod;
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++)
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
ll dp[2001];
ll rdp[2001];
ll inv[2002];

ll mod_pow(ll x, ll n = mod - 2) {
	ll ret = 1;
	while (n) {
		if (n % 2)ret = ret * x%mod;
		x = x * x%mod; n >>= 1;
	}
	return ret;
}
void init() {
	rep1(i, 2001) {
		inv[i] = mod_pow(i);
	}
}
void solve() {
	init();
	int n; ll d; int x;
	while (cin >> n >> d >> x, n) {
		x--;
		fill(dp, dp + n, 0);
		fill(rdp, rdp + n + 1, 1);
		dp[0] = 1; rdp[0] = 0;
		vector<ll> s;
		rep(i, n) {
			rep(j, n+1) {
				dp[j] = rdp[j];
				if (j >= x)dp[j] -= rdp[j - x];
				if (dp[j] < 0) {
					dp[j] += mod;
				}
			}
			s.push_back(dp[n]);
			rep(j, n) {
				rdp[j + 1] = rdp[j] + dp[j];
				if (rdp[j + 1] >= mod)rdp[j + 1] -= mod;
			}
		}
		ll p = d%mod;
		ll ans = 0;
		rep(i, s.size()) {
			if (i + 1 > d)continue;
			//cout << p << " " << s[i] << endl;
			ans += p * s[i]%mod; ans %= mod;
			p = p * ((d - 1 - i)%mod) % mod;
			p = p * inv[i + 2] % mod;
			//cout << i<<" "<<p << endl;
		}
		cout << ans << endl;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}



Measured memory_bytes: 3096
#include <iostream>

using namespace std;

int N;
int p[100005];

void swap(int i, int j)
{
	int tmp = p[i];
	p[i] = p[j];
	p[j] = tmp;
}

int main(void)
{
cin >> N;
for(int i = 0; i < N; i++) cin >> p[i+1];

int ans = 0;

for(int i = 1; i <= N; i++){
if(p[i] == i){
	
if(i == 1)swap(1, 2);
else if(i == N)	swap(N-1, N);
else{
	if(p[i+1] == i+1) swap(i, i+1);
	else{
		if(p[i+1] != i) swap(i, i+1);
		else swap(i, i-1);
	}
}
ans++;
}

}

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

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long ll;

int gcd(int a,int b)
{
    if(b > a)
    {
        swap(a,b);
    }

    if(b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
    
}

int main(void)
{
    int k;cin >>k;
    ll sum = 0;
    for (int a = 1; a <= k; a++)
    {
        for(int b = 1;b <= k;b++)
        {
            for(int c = 1;c <= k;c++)
            {
                sum += gcd(a,gcd(b,c));
            }
        }
    }
    cout << sum<<endl;
    return 0;
}

Measured memory_bytes: 3620
a,b,c,x,y = gets.split.map(&:to_i)
sum = a*x + b*y

(0..100000).each do |i|
  sum_a = 2*c*i + a*[0,x-i].max + b*[0,y-i].max
  sum = sum_a if sum > sum_a
end

puts sum

Measured memory_bytes: 3836
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

vector<vector<lli>> g;
map<lli,lli> d;
map<lli,lli> ans;
bool vis[200100];

void func(lli now,lli cost){
	if(vis[now])return;
	vis[now]=true;

	cost += d[now];
	ans[now] = cost;

	for(auto e:g[now]){
		func(e,cost);
	}
	return;
}

 
signed main(){
 
	lli n,q;
	cin>>n>>q;

	g.resize(n);

	REP(i,0,n-1){
		lli a,b;
		cin>>a>>b;
		a--,b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	REP(i,0,q){
		lli p,x;
		cin>>p>>x;
		p--;
		d[p]+=x;
	}

	func(0,0);
	for(auto e:ans){
		cout<<e.second<<" ";
	}
	cout<<endl;

 
	return 0;
}

Measured memory_bytes: 54144
//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#define ll long long
#define inf 20021225
#define N 100010
using namespace std;
ll read()
{
	ll s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
struct node{int id; ll d;}a[N];
bool operator<(node a,node b){return a.d<b.d;}
int sz[N],fa[N],n;
map<ll,int> f; ll d[N];
int edge[N][2]; ll val[N];
struct edge{int to,lt;}e[N]; int in[N],cnt;
void add(int x,int y){e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;}
void dfs(int x)
{
	sz[x]=1; d[x]=0;
	for(int i=in[x];i;i=e[i].lt)
		dfs(e[i].to),sz[x]+=sz[e[i].to],d[x]+=d[e[i].to];
	d[x]+=sz[x]-1;
}
void getd(int x)
{
	for(int i=in[x];i;i=e[i].lt)
		d[e[i].to]=d[x]+n-sz[e[i].to]*2,getd(e[i].to);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)	a[i].id=i,a[i].d=read(),f[a[i].d]=i;
	sort(a+1,a+n+1);
	for(int i=n;i>1;i--)
	{
		int x=a[i].id; ll w=a[i].d; sz[x]++;
		if(sz[x]>n/2)	return puts("-1"),0;
		if(w-n+sz[x]*2>=w||f.find(w-n+sz[x]*2)==f.end())	return puts("-1"),0;
		int fx=f[w-n+sz[x]*2]; sz[fx]+=sz[x]; fa[x]=fx; add(fa[x],x);
	}
	dfs(a[1].id); getd(a[1].id);
	for(int i=1;i<=n;i++)	if(a[i].d!=d[a[i].id])
		return puts("-1"),0;
	for(int i=2;i<=n;i++)
		printf("%d %d\n",fa[a[i].id],a[i].id);
	return 0;
}

Measured memory_bytes: 14208
import numpy as np
k,t=map(int,input().split())
a=list(map(lambda x:-int(x),input().split()))
a.sort()
import heapq
heapq.heapify(a)
b=heapq.heappop(a)
b+=1
while len(a)>0:
    c=heapq.heappop(a)
    if b<0:
        heapq.heappush(a,b)
    b=c+1
print(-b)

Measured memory_bytes: 12500
#include <stdio.h>
int main() 
{ signed long h,n; 
signed short temp; 
scanf("%ld%ld",&h,&n); 
while(n>0) { 
	scanf("%hd",&temp); 
	h = h - temp;
	n--; 
} 
if(h>0) { 
	printf("No"); 
}
else { printf("Yes"); 
} return 0; 
}


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

#define ipr pair<int, int>
#define pb push_back
#define ff first
#define ss second
#define fr(i, j, k) for (int i = j; i < k; i++)
#define rf(i, j, k) for (int i = j; i >= k; i--)
#define ll unsigned long long
#define int long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mp make_pair
#define cnt_ones(x) __builtin_popcountll(x)

#define IOS                           \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

const int Maxn = (int)1e5 + 1;
const ld pi = acos(-1);
const int mod = (int)1e9 + 7;
const int inf = (int)1e18;

template <class T>
ostream &operator<<(ostream &out, vector<T> &A) {
    fr(i, 0, (int)A.size()) out << A[i] << " ";
    return out;
}

int32_t main() {
    IOS int Q = 1;
    // cin >> Q;
    while (Q--) {
        int n;  cin>>n;
        vector<int> dp(2000+1,1);
        dp[0] = dp[1] = dp[2] = 0;
        dp[3] = 1;
        for(int i=4;i<=2000;i++){
            for(int j=3;j<i;j++){
                dp[i] = (dp[i] + dp[i-j])%mod;
            }
        }
        // fr(i,0,10)  cout << dp[i] <<" ";
        // cout << endl;
        cout << dp[n] << endl;
    }
    return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	t=1;
	while(t--)
	{
	    int n,k;
	    cin>>n>>k;
	    ll arr[n];
	    for(int i=0;i<n;i++)cin>>arr[i];
	    ll gr=1;
	    for(int i=k;i<n;i++){
	        //cout<<ngr<<" "<<gr<<endl;
	        if(arr[i]>arr[i-k]){
	            cout<<"Yes"<<endl;
	        }
	        else cout<<"No"<<endl;
	        //gr=ngr;
	    }
	}
	return 0;
}

Measured memory_bytes: 5200
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
 
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint 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(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
    
  int main(){
    lint n;
    cin >>n; vector<lint> a(n);
    rep(i,n)cin >> a[i];
    lint ans=0;
    lint l=0;
    lint r=0;
    lint count=0;
    lint sum=a[0];
    lint sumx=a[0];
    while(1){
        
        if(sum!=sumx){
            ans+=count;
            sum-=a[l];
            sumx^=a[l];
            count--;
            l++;
        }else {count++;
        if(r==(n-1))break;
        r++;
        sum+=a[r];
        sumx^=a[r];
        }
       // cout<<sum<<" "<<sumx<<" "<<count<<" "<<ans<<endl;
    }
    ans+=count*(count+1)/2;
    cout<<ans<<endl;
   
  }
  
     


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
  	public static void main(String... args) {
      	try (Scanner sc = new Scanner(System.in)) {
      	int H = sc.nextInt();
      	int W = sc.nextInt();
      	int h = sc.nextInt();
      	int w = sc.nextInt();
      	System.out.println((H - h) *(W - w));
        }
    }
}

Measured memory_bytes: 23764
A,B,C,X,Y = map(int,input().split())
if A + B < 2 * C:
    ans = A * X + B * Y
else:
    ans = min(X,Y) * 2 * C
    if X < Y:
        Z = Y - X
        ans += Z * min(B,2*C)
    else:
        Z = X - Y 
        ans += Z * min(A,2*C)
print(ans)

Measured memory_bytes: 3064
def get_primes(targ):
    '''
    素因数分解
    '''
    primes = []

    target = targ
    i = 2
    cnt = 0

    while (i * i) <= target:
        if(target % i) == 0:
            while(target % i) == 0:
                target //= i
                cnt += 1
            primes.append([i, cnt])
            cnt = 0
        else:
            i += 1

    if target != 1:
        primes.append([target, 1])

    return primes;

def ABC142D_DisjointSetOf():
    A, B = list(map(int, input().strip().split()))

    prA = get_primes(A)
    prB = get_primes(B)

    prAlist = [num[0] for num in prA]
    ans = 0
    for num in prB:
        if(num[0] in prAlist):
            ans += 1

    print(ans + 1)

def main():
    ABC142D_DisjointSetOf()

if __name__ == "__main__":
    main()


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

#define REP(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#define REPN(i, m, n) for(int (i)=(int)(m); (i)<(int)(n); (i)++)
#define REP_REV(i, n) for(int (i)=(int)(n)-1; (i)>=0; (i)--)
#define debug(x) cout << #x << ": " << (x) << endl;

using namespace std;

int main() {
//    ifstream in("C:\\Users\\P218024\\Documents\\Cpp Projects\\abc094\\sample.txt");
//    cin.rdbuf(in.rdbuf());

    int n;
    cin >> n;

    int X[n] = {0};
    int X_copy[n] = {0};
    REP(i,n) {
        cin >> X[i];
        X_copy[i] = X[i];
    }

    sort(X, X+n);

    int a = X[n / 2 - 1];
    int b = X[n / 2];
    REP(i, n) {
        cout << ((X_copy[i] < b) ? b : a) << endl;
    }

}

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

int main(){
	int H , W;
	int i, j;
	while(1){
		char fig1[301]={0};
		char fig2[301]={0};
		cin >> H >> W;
		if(H==0 && W==0) break;
		for(i=0 ; i<W ; i++){
			fig1[i]='#';
		}
		fig2[0]='#';
		fig2[W-1]='#';
		for(i=1 ; i<W-1 ; i++){
			fig2[i]='.';
		}
		cout << fig1 << endl;
		for(i=0 ; i<H-2 ; i++){
			cout << fig2 << endl;
		}
		cout << fig1 << endl;
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100000000;

int main()
{
   string s,t;
   cin >> s >> t;
   int sn =s.size(),tn = t.size();

   if(sn<tn)
   {
      cout<<"UNRESTORABLE"<<endl;
      return 0;
   }

   for(int i = sn-tn;i>=0;i--)
   {
      bool is = true;
      int a;
      rep(j,tn)
      {
         //cout<<t[j]<<s[i+j]<<endl;
         
         if(s[i+j]!='?'&&t[j]!=s[i+j])
         {
            is = false;
            
         }
      }
      if(is)
      {
         a=i;
         //cout<<a<<endl;
         rep(ii,sn)
         {
            if(ii<i||ii>=i+tn)
            {
               if(s[ii]=='?')
               cout<<'a';
               else
               {
                  cout<<s[ii];
               }
               
            }
            else
            {
               cout<<t[ii-i];
            }
            
         }
         cout<<endl;
         return 0;
      }
   }
   cout<<"UNRESTORABLE"<<endl;
   return 0;
}

Measured memory_bytes: 256