akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;

vector<int> par, rank, size;

void init(int n){
	par = vector<int>(n);
	rank = vector<int>(n);
	size = vector<int>(n);
	for(int i = 0; i < n; ++i){
		par[i] = i;
		rank[i] = 0;
		size[i] = 1;
	}
}

int find(int x){
	if(par[x] == x){
		return x;
	}else{
		return par[x] = find(par[x]);
	}
}

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

bool same(int x, int y){
	return find(x) == find(y);
}

int main(){
	int n;
	scanf("%d", &n);
	vector<pipii> edges(n - 1);
	init(n);
	for(int i = 0; i + 1 < n; ++i){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		edges[i] = pipii(c, pii(a, b));
	}
	sort(edges.begin(), edges.end());
	ll answer = 0;
	for(int i = 0; i + 1 < n; ++i){
		int a = edges[i].second.first, b = edges[i].second.second;
		ll c = edges[i].first;
		int as = size[find(a)];
		int bs = size[find(b)];
		answer += c * as * bs;
		unite(a, b);
	}
	printf("%lld\n", answer);
	return 0;
}

Measured memory_bytes: 6504
#include<cstdio>
#include<cstring>
const int N=57;
struct node
{
	int to,next;
}e[N*N];
int first[N],cnt;
inline void insert(int u,int v)
{
	e[++cnt]=(node){v,first[u]};first[u]=cnt;
	e[++cnt]=(node){u,first[v]};first[v]=cnt;
}
int dfn[N],low[N];
int sum;
inline int min(int a,int b)
{
	return a<b?a:b;
}
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++cnt;
	for(int k=first[x];k;k=e[k].next)
	{
		if(!dfn[e[k].to])	
		{
			tarjan(e[k].to,x),low[x]=min(low[x],low[e[k].to]);
			if(low[e[k].to]>dfn[x])		sum++;
		}
		else if(e[k].to!=fa)	low[x]=min(low[x],dfn[e[k].to]);
	}
}
int main()
{
	int n,m,u,v;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)	scanf("%d %d",&u,&v),insert(u,v);
	cnt=0;
	for(int i=1;i<=n;i++)	if(!dfn[i])	tarjan(i,-1);
	printf("%d\n",sum);
	return 0;
}

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

struct rtree{
  int org;
  int rig;
  int lef;
};

int main(){
  vector<rtree> node;
  tuple<int,int> id_and_pre_id;
  int n,root_id=0;

  cin >> n;
  node.resize(n);
  for(int i=0;i<n;i++){
    node[i].org = node[i].rig = node[i].lef = i;
  }

  for(int i=0;i<n;i++){
    int id,left,right;
    
    cin >> id >> left >> right;
    if(left != -1){
      node[id].lef = left;
      node[left].org = id;
    }
    if(right != -1){
    node[id].rig = right;
    node[right].org = id;
    }
  }

  while(root_id != node[root_id].org){
    root_id = node[root_id].org;
  }
  
  id_and_pre_id = make_tuple(root_id, -1);
  cout << "Preorder" << endl << " " << root_id;
  do{
    int id = get<0>(id_and_pre_id);
    int pre_id = get<1>(id_and_pre_id);

    if((id!=node[id].lef) && (pre_id!=node[id].lef) && (pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].lef,id);
      cout << " " << node[id].lef;
    }else if((id!=node[id].rig) && (pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].rig,id);
      cout << " " << node[id].rig;
    }else{
      id_and_pre_id = make_tuple(node[id].org,id);
    }
    
  }while(get<0>(id_and_pre_id) != get<1>(id_and_pre_id));

  id_and_pre_id = make_tuple(root_id,-1);
  cout << endl << "Inorder" << endl;
  do{
    int id = get<0>(id_and_pre_id);
    int pre_id = get<1>(id_and_pre_id);

    if((id!=node[id].lef) && (pre_id!=node[id].lef) && (pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].lef,id);
    }else if((id!=node[id].rig) && (pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].rig,id);
      cout << " " << id;
    }else if((pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].org,id);
      cout << " " << id;
    }else{
      id_and_pre_id = make_tuple(node[id].org,id);
    }
    
  }while(get<0>(id_and_pre_id) != get<1>(id_and_pre_id));

  id_and_pre_id = make_tuple(root_id, -1);
  cout << endl << "Postorder" << endl;
  do{
    int id = get<0>(id_and_pre_id);
    int pre_id = get<1>(id_and_pre_id);

    if((id!=node[id].lef) && (pre_id!=node[id].lef) && (pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].lef,id);
    }else if((id!=node[id].rig) && (pre_id!=node[id].rig)){
      id_and_pre_id = make_tuple(node[id].rig,id);
    }else{
      id_and_pre_id = make_tuple(node[id].org,id);
      cout << " " << id;
    }
  }while(get<0>(id_and_pre_id) != get<1>(id_and_pre_id));
  cout << endl;
}


Measured memory_bytes: 3112
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
    long long a,b,cnt=0,m=0;
    scanf("%lld%lld",&a,&b);
    long long k=__gcd(a,b);
    cnt++;
    for(long long i=2;i<=(int)sqrt(k);i++)
    {
        if(k%i==0)
        {
            cnt++;
        }
        while(k%i==0)
        {
            k/=i;
        }
    }
    if(k>1)
    {
        cnt++;
    }
    printf("%lld\n",cnt);
    return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

int a[MAXN], b[MAXN];

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 0, n){
		scanf("%d%d", &a[i], &b[i]);
	}
	ll add = 0ll;
	for(int i = n - 1; i >= 0; i--){
		ll q = (a[i] + add + b[i] - 1) / b[i];
		ll dd = q * b[i] - (a[i] + add);
		add += dd;
	}
	printf("%lld\n", add);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 1024
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        long N;
        N = sc.nextLong();
        solve(N);
    }

    static void solve(long N){
        System.out.println((int)(Math.pow(N, 3)));

    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int n,x,t;cin>>n>>x>>t;
    if(n%x==0){
        cout<<n/x*t<<endl;
    }else{
        cout<<(n/x+1)*t<<endl;
    }




    
}


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

int main() { 
    int64_t A;
    cin >> A;
    double B;
    cin >> B;
    B *= 100;
    A *= stoi(to_string(B));
    A /= 100;
    cout << A << endl;
}

Measured memory_bytes: 3824
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

int ans;
int N, Y;


int main(void) {
    scanf("%d %d", &N, &Y);
    Y /= 1000;
    for (int x = 0; x <= N; x++) {
      for (int y = 0; x+y <= N; y++) {
        int z = N - x - y;
        if (Y == x*10 + y*5 + z) {
          printf("%d %d %d\n", x, y, z);
          return 0;
        }
      
      }
    
    }
      
    
   puts("-1 -1 -1");
   return 0;
}


Measured memory_bytes: 256
N=int(input())
h=list(map(int,input().split()))
dp=[float('inf') for i in range(N)]
dp[0]=0
for i in range(1,N):
  dp[i]=min(dp[i],dp[i-1]+abs(h[i]-h[i-1]))
  if(i>1):
    dp[i]=min(dp[i],dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N-1])

Measured memory_bytes: 13928
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 客:N人　バスの定員:C人　limit:K分
N, C, K = getNM()
T = getArray(N)
T.sort()

pas = 1
time = T[0]
ans = 1

for i in range(1, N):
    # 乗客が満杯だと
    if pas >= C:
        # バス増便
        ans += 1
        pas = 1
        time = T[i]
        continue

    # i人目を乗せた時制限時間を過ぎるようなら
    if T[i] > time + K:
        # バス増便
        ans += 1
        pas = 1
        time = T[i]
        continue

    # 上の二つの条件に引っかからないなら
    pas += 1

print(ans)

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;

const int maxn = 1e5 + 5;

int a[maxn];
int k;
int n;

ll pre[maxn], suf[maxn];
ll sum[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    pre[0] = 0;suf[n + 1] = 0;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        pre[i] = pre[i - 1] + max(0, a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    for(int i = n;i >= 1;i--){
        suf[i] = suf[i + 1] + max(0, a[i]);
    }
    ll ans = 0;
    for(int i = 1;i + k - 1 <= n;i++){
        ll tmp = max(sum[i + k - 1] - sum[i - 1], 0LL) + pre[i - 1] + suf[i + k];
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2944
W,H,N = map(int, input().split())
bottom = [0, 0]
top = [W,H]

for _ in range(N):
    x,y,a = map(int, input().split())
    if a==1:
        bottom[0] = max(bottom[0], x)
    elif a==2:
        top[0] = min(top[0], x)
    elif a==3:
        bottom[1] = max(bottom[1], y)
    elif a==4:
        top[1] = min(top[1], y)

print(max(0, top[0]-bottom[0])*max(0,top[1]-bottom[1]))


Measured memory_bytes: 3064
n,m = map(int,input().split())
a = []
a = list(map(int,input().split()))

b = sum(a)/(4.0*m)
c = 0
for i in range(n) :
    if a[i]>=b :
        c += 1

if c>=m :
    print('Yes')
else :
    print('No')


Measured memory_bytes: 3060
def cro(a,b,c)
  x1 = b[0]-a[0]
  y1 = b[1]-a[1]
  x2 = c[0]-a[0]
  y2 = c[1]-a[1]
  return x1*y2 - x2*y1
end

n = gets.to_i;
xmin = 10000
ymin = 10000
s=[]
n.times{s << gets.split.map(&:to_f)}
s = s.sort_by {|x| [x[0], x[1]]}
temp = s.sort_by {|x| [x[1], x[0]]}
#puts temp.join(" ")
#puts s.join(" ")
u=[]; u << s[0]; u << s[1]
l=[]; l << s[-1]; l << s[-2]

for i in 2..(s.size-1) do
  (u.size).downto(2){|n|
#    puts "u"
#    puts u[n-2].join(" ")
#    puts u[n-1].join(" ")
    break if !(n>=2 && cro(u[n-2], u[n-1], s[i]) > 0)
    u.pop
  }
#  puts "s"
#  puts s[i].join(" ")
  u << s[i]
end

(s.size-3).downto(0){|i|
  (l.size).downto(1){|n|
    break if !(n >= 2 && cro(l[n-2], l[n-1], s[i]) > 0)
#    puts "i:#{i} n:#{n}"
    l.pop
  }
  l << s[i]
}

ans = (u+l).uniq.reverse
puts ans.size
while ans[0] != temp[0]
  ans.push(ans.shift)
end
ans.each{|a|
  puts a.map(&:to_i).join(" ")
}



Measured memory_bytes: 23480
#include<stdio.h>

int selectSort(int A[], int N){
  int i,j,t,sw =0,minj;
  for (i=0;i<N-1;i++){
    minj =i;
    for (j=i; j<N; j++){
      if(A[j]<A[minj]) minj = j;
    }
    t = A[i];A[i]=A[minj];A[minj]=t;
    if(i != minj ) sw++;
    }
  return sw;
}

int main(){
  int A[100],N,i,sw;
  scanf("%d", &N);
  for (i=0; i<N;i++) scanf("%d", &A[i]);

  sw = selectSort(A,N);

  for (i=0; i<N;i++){
    if (i>0) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
  printf("%d\n", sw);
  return 0;
}

Measured memory_bytes: 2728
A, B, C, D = input()
for i in range(2**3):
    ans =["+", "+", "+"]
    for j in range(3):
        if (i>>j) & 1:
            ans[j] = "-"
    if eval(A+ans[0]+B+ans[1]+C+ans[2]+D) ==7:
        print(A+ans[0]+B+ans[1]+C+ans[2]+D+'=7')
        break

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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c; cin>>a>>b>>c;
    string ans;
    if(a==b&&b==c&&c==a) ans="No";
    else if(a==b||b==c||c==a) ans = "Yes";
    else ans = "No";
    print(ans);
    return 0;
}

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

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

struct Edge {
    int src, dst;
    Edge(int src, int dst): src(src), dst(dst) {}
};
using Vertex = vector<Edge>;
using Graph = vector<Vertex>;

void add_edge(Graph& graph, int src, int dst) {
    graph[src].emplace_back(src, dst);
    graph[dst].emplace_back(dst, src);
}

bool augment(const Graph& graph, vector<bool>& visited, vector<int>& match, int u) {
    if (u == -1) return true;
    for (auto& e : graph[u]) {
        if (!visited[e.dst]) {
            visited[e.dst] = true;
            if (augment(graph, visited, match, match[e.dst])) {
                match[e.src] = e.dst;
                match[e.dst] = e.src;
                return true;
            }
        }
    }
    return false;
}

int bipartie_matching(const Graph& graph, int n_left) {
    vector<int> match(graph.size(), -1);
    int n_match = 0;
    REP(u, n_left) {
        vector<bool> visited(graph.size());
        if (augment(graph, visited, match, u)) ++n_match;
    }
    return n_match;
}

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a%b); }

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

    int m, n;
    while (cin>>m>>n, m|n) {
        vector<int> blue(m), red(n);
        REP(i, m) cin >> blue[i];
        REP(i, n) cin >> red[i];

        Graph graph(m+n);
        REP(i, m) REP(j, n) {
            if (gcd(blue[i], red[j]) > 1)
                add_edge(graph, i, m+j);
        }

        cout << bipartie_matching(graph, m) << '\n';
    }
}

Measured memory_bytes: 5812
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (ll i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define re0 return 0
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define Rev(a) reverse(a.begin(), a.end())
#define MATHPI acos(-1)
#define itn int
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-19;


signed main() {
    ll n;
    cin >> n;
    vll a(n); 
    ll ans = 0;
    ll sum = 0;
    rep(i, n) {
        cin >> a[i];
        sum += a[i]; //MOD=1e9+7
        sum %= MOD;
    }
    rep(i, n) {
        sum -= a[i];
        if (sum < 0) sum += MOD;
        ans += (a[i] * sum);
        ans %= MOD;    
    }
    cout << ans << endl;
}

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

#define int long long

const int maxn = 50, lg = 6;
vector <int> adj[maxn];
int par[maxn][lg], h[maxn], V[maxn], U[maxn];
bitset <maxn> mark[1 << 20];

void dfs(int v, int p = -1) {
	par[v][0] = p;
	fill(par[v] + 1, par[v] + lg, -1);
	for (int i = 1; i < lg; i++) {
		if (par[v][i - 1] == -1)
			break;
		par[v][i] = par[par[v][i - 1]][i - 1];
	}
	for (auto u: adj[v]) {
		if (u != p) {
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
}

int get_par(int v, int d) {
	for (int i = 0; i < lg; i++) {
		if (d & (1 << i))
			v = par[v][i];
	}
	return v;
}

int lca(int v, int u) {
	if (h[v] > h[u])
		swap(v, u);
	u = get_par(u, h[u] - h[v]);
	if (v == u)
		return v;
	for (int i = lg - 1; i >= 0; i--) {
		if (par[v][i] != par[u][i]) {
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

int32_t main() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int v, u;
		cin >> v >> u;
		v--;
		u--;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	dfs(0);
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> V[i] >> U[i];
		V[i]--;
		U[i]--;
	}
	int ans = 1ll << (n - 1);
	for (int mask = 1; mask < (1 << m); mask++) {
		mark[mask] = mark[mask - (mask & -mask)];
		int v = V[__builtin_ctz(mask)], u = U[__builtin_ctz(mask)];
		int x = lca(v, u);
		while (v != x) {
			mark[mask][v] = 1;
			v = par[v][0];
		}
		while (u != x) {
			mark[mask][u] = 1;
			u = par[u][0];
		}
		if (__builtin_popcount(mask) % 2)
			ans -= 1ll << (n - 1 - mark[mask].count());
		else
			ans += 1ll << (n - 1 - mark[mask].count());
	}
	cout << ans;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=5010;
int n,a,b,x,p[N];
ll dp[N][N];
int main() {
	scanf("%d%d%d",&n,&a,&b);
	rep(i,1,n+1) scanf("%d",&x),p[x]=i;
	memset(dp,0x20,sizeof(dp));
	dp[0][0]=0;
	rep(i,1,n+1) rep(j,0,i) {
		if (p[i]>p[j]) {
			dp[i][i]=min(dp[i][i],dp[i-1][j]);
			dp[i][j]=min(dp[i][j],dp[i-1][j]+b);
		} else
			dp[i][j]=min(dp[i][j],dp[i-1][j]+a);
	}
	printf("%lld\n",*min_element(dp[n],dp[n]+n+1));
}


Measured memory_bytes: 196480
h, w = [int(x) for x in raw_input().split()]
def d(a, b):
  c = h * w - a - b
  if min(a, b, c) <= 0: return float("inf")
  return max(a, b, c) - min(a, b, c)
w2 = w // 2
w3 = w // 3
h2 = h // 2
h3 = h // 3
print min(
  d(h * w3, h * w3),
  d(h * w3, h * (w3 + 1)),
  d(h * w3, h2 * (w - w3)),
  d(h * (w3 + 1), h2 * (w - w3 - 1)),
  d(w * h3, w * h3),
  d(w * h3, w * (h3 + 1)),
  d(w * h3, w2 * (h - h3)),
  d(w * (h3 + 1), w2 * (h - h3 - 1))
)

Measured memory_bytes: 2696
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

constexpr int inf = 2147483647;
constexpr int64_t inf64 = 9223372036854775807;
constexpr int mod = 1e9+7;

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

  string s, t;
  cin >> s >> t;
  t.pop_back();
  YesorNo(s == t);
  return 0;
}

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

#define cel(n, k) ((n-1)/k+1)
#define sets(a) memset(a, 1, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << "Line " << __LINE__ <<": " << x << nl
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define nl "\n"
#define sp " "

#define _ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define file() freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout), cout << "File" << nl

typedef long long ll;
typedef pair<ll,int> pli;

const int N = 305;

int tc = 1;

int n;

int main(){_

    //file();

    //cin >> tc;

    while(tc--){

        cin >> n;

        cout << (1000-n%1000)%1000 << nl;
        
        
    }  
    

    return 0;
        
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_N = int(1e5) + 5;
const double EPS = 1e-8;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#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 (ll i = m; i < n; i++)

int h, w, n;
int si[10],sj[10];
int d[1005][1005];
string s[1005];

int bfs(int k) {
    REP(i,h)fill(d[i],d[i]+w,IINF);
    queue<P> que;
    d[si[k]][sj[k]] = 0;
    que.push({si[k],sj[k]});
    while(!que.empty()){
        P p = que.front();
        que.pop();
        int y = p.first, x = p.second;
        REP(m,4){
            int ny = y + dy[m], nx = x + dx[m];
            if (ny < 0 || ny >= h) continue;
            if (nx < 0 || nx >= w) continue;
            if (s[ny][nx] == 'X') continue;
            if(d[ny][nx] == IINF){
                d[ny][nx] = d[y][x] + 1;
                if(si[k+1]==ny && sj[k+1]==nx)return d[ny][nx];
                que.push({ny,nx});
            }
        }
    }
}

int main() {
    cin >> h >> w >> n;
    REP(i, h) {
        cin >> s[i];
        REP(j,w){
            if(s[i][j]=='S'){
                si[0] = i;
                sj[0] = j;
            }
            if(s[i][j]>='1' && s[i][j]<='9'){
                int x = s[i][j] - '0';
                si[x] = i;
                sj[x] = j;
            }
        }
    }
    int ans = 0;
    REP(i,n){
        ans += bfs(i);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 8040
#include <bits/stdc++.h>
using namespace std;
  
int main(){
  int n, a;
  cin >> n;
  int c[3] = {}; 
  for(int i = 0; i < n; i++){
    cin >> a;
    int cnt = 0;
    while(a % 2 == 0 && cnt != 2){
      cnt++;
      a /= 2;
    }
    c[cnt]++;
  }
  if(c[1] == 0){
    cout << (c[0] <= c[2] + 1 ? "Yes" : "No") << endl;
  }else{
    cout << (c[0] <= c[2] ? "Yes" : "No") << endl;
  }
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int n,m,a;
	while(cin>>n>>m>>a){
		if(n==0) break;
		int ys[3][m],hmax;
		for(int i=0;i<m;i++){
			cin>>ys[0][i]>>ys[1][i]>>ys[2][i];
			hmax=max(hmax,ys[0][i]);
		}
		for(int i=hmax;i>0;i--){
			for(int j=0;j<m;j++){
				if(ys[0][j]==i){
					if(ys[1][j]==a){
						a=ys[2][j];
						goto end;
					}
					else if(ys[2][j]==a){
						a=ys[1][j];
						goto end;
					}
				}
			}
			end:;
		}
		cout<<a<<endl;
	}
    return 0;
}

Measured memory_bytes: 1168
using DataStructures
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  A,B,C,D = readint() 

  E = B - A + 1

  divC = B÷C - (A-1)÷C
  divD = B÷D - (A-1)÷D

  cd = C*D÷gcd(C,D)
  divCD = B÷cd - (A-1)÷cd

  println(E-divC-divD + divCD)
  
end



main()

Measured memory_bytes: 186832
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cmath>
#include <set>

using namespace std;

uint64_t a[100'000];
uint64_t b[100'000];
uint64_t psum[100'000];
uint64_t psumA[100'000];
uint64_t m[100'000];

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

    for (int i = 0; i < n; i++)
    {
        b[i] = a[i * 2 % n];
    }

    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            psum[i] = 0;
            for (int j = 0; j <= n / 2; j++)
            {
                psum[i] += b[i + j];
            }
            continue;
        }
        psum[i] = psum[(i - 1) % n] + b[(i + n / 2) % n] - b[(i - 1) % n];
    }

    for (int i = 0; i < n; i++)
    {
        psumA[i * 2 % n] = psum[i];
    }

    uint64_t s = 0;
    for (int i = 0; i < n; i++)
    {
        s += a[i];
    }

    for (int i = 0; i < n; i++)
    {
        m[i] = 2LL * psumA[i] - s;
    }

    for (int i = 0; i < n; i++)
    {
        cout << m[i] << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 5248
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        int[] b = new int[m];
        for(int i = 0; i < m; i++){
            b[i] = Integer.parseInt(sc.next());
        }
        int[][] a = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                a[i][j] = Integer.parseInt(sc.next());
            }
        }
        
        int count = 0;
        for(int i = 0; i < n; i++){
            int code = c;
            for(int j = 0; j < m; j++){
                code += a[i][j] * b[j];
            }
            if(code > 0){
                count++;
            }
        }
        
        System.out.println(count);
    }
}

Measured memory_bytes: 21716
/*
Iroha's Obsession
*/

#include <iostream>
#include <vector>
#include <stack>

std::string solve(std::stack<int> s, std::vector<int> digs, int comp)
{
    std::string res = "";
    if (comp>0)
    {
        while (!s.empty())
        {
            res.append(std::to_string(digs[0]));
            s.pop();
        }
        return res;
    }
    int d = s.top();
    s.pop();
    for (int i=0; i<digs.size(); i++)
    {
        if (digs[i]<d) continue;
        res.append(std::to_string(digs[i]));
        if (digs[i]==d)
        {
            if (s.empty()) { return res; }
            else
            {
                std::string rem = solve(s, digs, 0);
                if (rem == "-") return rem;

                res.append(rem);
                return res;
            }
        }
        else
        {
            res.append(solve(s, digs, 1));
            return res;
        }
    }
    return "-";
}

int solve(int N, std::vector<int> digs)
{
    int F = N;
    std::stack<int> s;
    while (F>0)
    {
        int d = F%10;
        s.push(d);
        F /= 10;
    }
    std::string res = solve(s, digs, 0);
    if (res == "-")
    {
        int n = digs[0];
        if (n==0) n = digs[1];
        while (N>0)
        {
            n *= 10;
            n += digs[0];
            N /= 10;
        }
        return n;
    }
    else
    {
        return stoi(solve(s, digs, 0));
    }
}

int main()
{
    std::vector<bool> allowed;
    for (int d=0; d<10; d++) allowed.push_back(true);

    int N, K, D;
    std::cin >> N >> K;
    for (int i=0; i<K; i++)
    {
        std::cin >> D;
        allowed[D] = false;
    }
    std::vector<int> digs;
    for (int d=0; d<10; d++)
    {
        if (allowed[d])
        {
            digs.push_back(d);
        }
    }

    int res = solve(N, digs);
    std::cout << res << "\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<numeric>

using namespace std;

int main(){
	int n,m;
	cin >> n;
	cin >> m;
	vector<int> vote;
	int input;
	while(cin >> input){
		vote.push_back(input);
	}
	int sum = accumulate(vote.begin(), vote.end(), 0);
	float measure = sum;
	int count=0;
	for(auto it :vote){
		if(it*4*m >= sum) count++;
	}
	
	if(count >= m) cout << "Yes";
	else cout << "No";
	
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <limits>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdint>
#include <functional>
#define rep(i, s, g) for (i = s; i < g; i++)
using namespace std;
using ll = long long;

const ll mod = 1000000000 + 7; //10^9

int main() {
    int D,T,S;
    cin >> D >> T >> S;
    int a = D - T*S;
    if(a > 0){
        cout << "No" << endl;
    }else
    {
        cout << "Yes" << endl;
    }
    

    
    
    
}

Measured memory_bytes: 3596
str1 = input()
val = len(str1)
if len(str1) % 2!= 0:
    if str1 == str1[::-1]:
        half = str1[:int((val-1)/2)]
        shalf = str1[int((val+3)/2) -1:]
        if half == half[::-1] and shalf == shalf[::-1]:
            print("Yes")
        else:
            print("No")
    else:
        print("No")



Measured memory_bytes: 3064
#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
//#pragma GCC target ("avx2,tune=native")
#include<bits/stdc++.h>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define __V vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define oit ostream_iterator
#define mod 1000000007ll
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
	in >> a.first >> a.second;
	return in;
}
template<typename T>
void getv(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
	v.resize(n);
	for (auto& i : v)
		getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
	v.resize(n + 1);
	for (int i = 1; i <= n; i++)
		getv1(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &x) {
	while (x = getchar_unlocked(), x < 33) {
		;
	}
}
inline void getstr(string &str) {
	str.clear();
	char cur;
	while (cur = getchar_unlocked(), cur < 33) {
		;
	}
	while (cur > 32) {
		str += cur;
		cur = getchar_unlocked();
	}
}
template<typename T> inline bool sc(T &num) {
	bool neg = 0;
	int c;
	num = 0;
	while (c = getchar_unlocked(), c < 33) {
		if (c == EOF)
			return false;
	}
	if (c == '-') {
		neg = 1;
		c = getchar_unlocked();
	}
	for (; c > 47; c = getchar_unlocked())
		num = num * 10 + c - 48;
	if (neg)
		num *= -1;
	return true;
}
template<typename a, typename b>
void minq(a& x, b y) {
	if (x > y)
		x = y;
}
template<typename a, typename b>
void maxq(a& x, b y) {
	if (x < y)
		x = y;
}
typedef unsigned long long ull;
typedef long long ll;
typedef float ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
uniform_real_distribution<double> double_dist(0, 1);
//WHEN DOING MODULAR SUBTRACTION ALWAYS **ALWAYS** ADD MOD
//no AVX on ATCoder
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {
	doin();
	int n;
	cin >>n;
	vi a;
	getv(a, n);
	sort(all(a));
	int x = a.back(), y = 0;
	a.pop_back();
	for(auto i : a) if(abs(x-2*i) < abs(x-2*y)) y = i;
	cout << x << " " << y;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

void split(std::vector<std::string>& tmp, std::string& str,char delimiter);

int main(){
    int cnt = 0;
    bool odd;
    std::string str1;
    std::string str2;
    std::string tmp1;
    std::string tmp2;
    while(true){
        cnt = 0;
        odd = false;
        std::cin >> str1;
        if(str1 == "."){
            break;
        }
        std::vector<std::string> tmp1;
        split(tmp1,str1,'"');
        std::cin >> str2;
        std::vector<std::string> tmp2;
        split(tmp2,str2,'"');
        int size = tmp1.size();
        int size2 = tmp2.size();
        if(size != size2){
            cnt += 2;
        }else{
            for(int i=0;i<size;i++){
                if(tmp1[i]!=tmp2[i]){
                    if(odd){
                        cnt++;
                    }else{
                        cnt += 2;
                        break;
                    }
                }
                if(odd){
                    odd = false;
                }else{
                    odd = true;
                }
            }
        }
        
        if(cnt==0){
            std::cout << "IDENTICAL\n";
        }else if(cnt==1){
            std::cout << "CLOSE\n";
        }else{
            std::cout << "DIFFERENT\n";
        }
    }
}



void split(std::vector<std::string>& tmp, std::string& str,char delimiter){
    std::istringstream iss(str);
    std::string item;
    while(std::getline(iss,item,'"')){
        tmp.push_back(item);
    }
}



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

const int maxN = 5e5+5;

int A[maxN], n, q, last[maxN], ANS[maxN];
vector<pair<int, pair<int, int>>> queries;

const int LEAF = (1 << 19);
int TREE[LEAF*2];

void update(int v, int x){
    v += LEAF;
    while(v >= 1){
        TREE[v] += x;
        v /= 2;
    }
}

int query(int l, int r){
    int ans = 0;
    l += LEAF;
    r += LEAF;
    ans += TREE[l];
    if(l != r)
        ans += TREE[r];
    while(l / 2 != r / 2){
        if(l%2 == 0)
            ans += TREE[l+1];
        if(r%2 == 1)
            ans += TREE[r-1];
        l /= 2;
        r /= 2;
    }
    return ans;
}


void solve(){
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> A[i];
        last[i] = -1;
    }
    last[n] = -1;
    for(int i = 0; i < q; i++){
        int a, b;
        cin >> a >> b;
        queries.push_back({b, {a, i}});
    }
    sort(queries.begin(), queries.end());
    int curr = -1;
    for(int i = 0; i < queries.size(); i++){
        int l = queries[i].second.first, r = queries[i].first;
        l--; r--;
        while(curr != r){
            curr++;
            int val = A[curr];
            if(last[val] != -1)
                update(last[val], -1);
            update(curr, 1);
            last[val] = curr;
        }
        ANS[queries[i].second.second] = query(l, r);
    }
    for(int i = 0; i < q; i++)
        cout << ANS[i] << "\n";
}


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

    bool multitest = false;
    //multitest = true;
    if(multitest){
        int t; cin >> t;
        while(t--)
            solve();
    }
    else
        solve();
}






Measured memory_bytes: 19584
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
 
// ===============================================================
 
using namespace std;
using ll = long long;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vs = vector<string>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using vm = vector<short>;
using vmm = vector<vector<short>>;
using pii = pair<int, int>;
using psi = pair<string, int>;
using ld = long double;
using ull = unsigned long long;
 
// ===============================================================
 
ll gcd(ll a, ll b)
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}
//最大公約数
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
//最小公倍数
ll box(double a) 
{
	ll b = a;
	return b;
}
//切り捨て
ll fff(double a) 
{
	ll b = a + 0.5;
	return b;
}
//四捨五入
ll sum(ll n) { 
	return (1 + n) * n / 2;
}
//1から整数nまでの合計
bool prime(ll a)//素数判定、primeならtrue,違うならfalse
{
	if (a < 2) return false;
	else if (a == 2) return true;
	else if (a % 2 == 0) return false;
	double sqrtNum = sqrt(a);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (a % i == 0)
		{
			return false;
		}
	}
 
	// 素数である
	return true;
}
//素数判定
 
// ===============================================================
 
int main() {
	ll n, m;
	cin >> n >> m;
	vl a(n);
	vl r(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			r[i] = a[i];
		}
		else r[i] = r[i - 1] + a[i];
	}
	ll ans = 0;
	ll count = 0;
	for (int i = 0; i < n - m+1; i++) {
		if (i != 0) {
			count = r[i + m - 1] - r[i - 1];
		}
		else {
			count = r[m - 1];
		}
		if (max(ans, count) == count) {
			ans = count;
		}
	}
	long double f = ans+m;
	printf("%.9Lf", f/2);
}

Measured memory_bytes: 6496
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

class DisjointSet
{
public:
    vector<int> rank, p;

    DisjointSet() {}
    DisjointSet(int size)
    : rank(vector<int>(size, 0)), p(vector<int>(size, 0))
    {
        for (int i = 0; i < size; ++i) makeSet(i);
    }

    void makeSet(int x)
    {
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y)
    {
        return findSet(x) == findSet(y);
    }

    void unite(int x, int y)
    {
        link(findSet(x), findSet(y));
    }

    void link(int x, int y)
    {
        if (rank[x] > rank[y])
        {
            p[y] = x;
        }
        else
        {
            p[x]  = y;
            if (rank[x] == rank[y])
            {
                ++rank[y];
            }
        }
    }

    int findSet(int x)
    {
        if (p[x] != x)
        {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};

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

    int N, M;
    cin >> N >> M;

    vector<int> p(N);
    rep (i, N) cin >> p[i];

    int x, y;
    DisjointSet ds{N + 1};
    rep (i, M)
    {
        cin >> x >> y;
        ds.unite(x, y);
    }

    int ans = 0;
    rep (i, N)
    {
        if (p[i] == i + 1 || ds.same(p[i], i + 1))
        {
            ++ans;
        }
    }

    cout << ans << "\n";
    return 0;
}



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

int main()
{
    long long int n, i, sum=0;

    cin>>n;

    for(i=1; i<=n; i++)
    {
        if(i%3!=0 && i%5!=0)
            sum = sum+i;
    }

    cout<<sum<<endl;

    return 0;
}


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

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

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    for(int i = K; i < N; i++){
        if(A[i-K] < A[i]) cout << "Yes" << endl;
        else cout <<"No" << endl;
    }
}


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

#define ll long long
#define an "\n";
#define pb push_back
#define pob pop_back

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, d, sum=0;
	cin >> n >> d;
	for(int i=0;i<n;i++) {
		int a, b;
		cin >> a >> b;
		if(sqrt(pow(a, 2)+pow(b, 2))<=d) {
			sum++;
		}
	}
	cout << sum;
}




Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define rep(i,a) for(int i=0;i<a;i++)
using namespace std;
 
using ll = long long;
 
 
ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r;
string s, t, u;
ll v, w, x, y, z;
 
int main() {
 
    cin >> n;
    r = n;
    for (i = 1; i * i <= n; ++i) {
        if (n % i) continue;
        r = min(r, i + n / i - 2);
    }
    cout << r << endl;
 
 
}

Measured memory_bytes: 3656
#define ENABLE_DEBUG 0
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/
u64 msb(u64 x){
    x|=x>>1; x|=x>>2; x|=x>>4;
    x|=x>>8; x|=x>>16; x|=x>>32;
    return x^x>>1;
}
int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    for(u64 i=0; i<5;i++)DEBUG(i,msb(i));

    usize t;
    std::cin >> t;
    while (t--) {
        usize n;
        std::cin >> n;
        vec<u64> a(n);
        for (u64& x: a) std::cin >> x;

        vec<usize> rank(n+1);
        for (usize i=n-1; i!=numr<usize>::max(); i--) {
            rank.at(i) = rank.at(i+1);
            u64 tester = msb(a.at(i));
            if (!tester) continue;
            rank.at(i)++;
            for (usize j=0; j<n; j++) if (j!=i && (a.at(j)&tester)) {
                a.at(j) ^= a.at(i);
            }
        }
        DEBUG(a);
        DEBUG(rank);

        std::string s;
        std::cin >> s;
        bool ans = 0;
        for (usize i=n-1; i!=numr<usize>::max(); i--) {
            if (s.at(i)=='1' && rank.at(i)!=rank.at(i+1)) {
                ans = 1;
                break;
            }
        }
        std::cout << ans << '\n';
    }
}


Measured memory_bytes: 3572
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n;
    cin>>n;
    vector<in> a(n);
        rep(i,n) cin>>a.at(i);
    in ans=0ll;
    in zero =0ll;
    REP(i,1,n){
        // ans += max(zero, a[i]-a[i-1]);
        // a[i]=max(a[i-1],a[i]);
        if(a[i-1]<=a[i]) continue;
        ans += a[i-1]-a[i];
        a[i]=a[i-1];
        int z=0;
    }
    cout<<ans<<endl;
}/*
./problem.exe
*/

Measured memory_bytes: 4756
mod = 10**9+7
n, m = list(map(int, input().split()))
dp = [0]*(n+1)
dp[0] = 1
s = set()
for i in range(m):
    a = int(input())
    s.add(a)

for i in range(n):
    if i in s:
        continue
    for j in range(1,3):
        if i+j <= n:
            dp[i+j] = (dp[i+j] + dp[i])%mod

print(dp[-1])

Measured memory_bytes: 51032
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 2 - 170;

int main() {
    int n, p = 0, q = INF<int>;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        p = max(p, a);
        q = min(q, b);
    }
    cout << p+q << "\n";
    return 0;
}


Measured memory_bytes: 256