akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;


const int INF = 10000000;
const long long INFL = (1LL<<40);
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

template< typename T >
struct edge{
    int src, to;T cost;
    edge(int to,T cost) :src(-1),to(to),cost(cost){}
    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}edge
    &operator=(const int &x){
        to =x;
        return *this;
    }
    operator int() const{ return to;}
};

double dist (double a, double b,  double c, double d){
    
    return sqrt((a-c)*(a-c) + (b-d)*(b-d));
    
}

bool check(int x,int y,vector<string> a,vector<string> b ){
    for(auto i = 0; i<b.size();i++){
        for(auto j =0; j<b.size();j++){
            if(a[x+i][y+j]!= b[i][j]) return false;
        }
    }
    return true;
}

int dist(pii a, pii b){
    return abs(a.first-b.first) + abs(a.second-b.second);
}


int main() {
    int x,y,z;cin>>x>>y>>z;
    x-=z;
    if(x<z) {cout<<0<<endl; return 0;}
    
    int count = 0;
    while(x-y>=z){x-=y+z;count++;}
    cout<<count<<endl;
    
    return 0;
}







Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<algorithm>
#define MOD 1000000007
using namespace std;

long long fact[200010];
long long a[200010];


long long powmod(long long a,long long b,long long N)
{
	long long result=1;
	a=a%N;
	while(b>0){
		if (b%2==1){
			result=result*a;
			result=result%N;
			b--;
		}
	
		b/=2;
		a=(a*a)%N;
		
	}
	return result;

}

long long comp(long long a, long long b, int p) {
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;
 
    int ans = 1, ca = 1, cb = 1;
    for(long long i = 0; i < b; ++i) {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*powmod(cb, p - 2, p)) % p;
    return ans;
}

long long lucas(long long n, long long m, long long p) {
     long long ans = 1;
 
     while(n&&m&&ans) {
        ans = (ans*comp(n%p, m%p, p)) % p;
        n /= p;
        m /= p;
     }
     return ans;
}


int main()
{
	long long n,a,b;
    int ans;
	cin>>n>>a>>b;
	ans=powmod(2,n,MOD)-1-lucas(n,a,MOD)-lucas(n,b,MOD);
	while(ans<0) ans+=MOD;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
s = sorted([int(input()) for _ in range(n)])

ans = sum(s)
s = [q for q in s if q % 10]
while ans % 10 == 0 and ans > 0:
    if not s:
        ans = 0
        break
    ans -= min(s)
    s.remove(min(s))
print(ans)

Measured memory_bytes: 3064
n=int(input())
l=list(map(int,input().split()))
ret=[0]*n
now=1
for i in range(max(l).bit_length()):
    z=0
    for j in range(n):
        if l[j]%2:
            z+=1
    for j in range(n):
        ret[j]+=(l[j]%2+z)%2*now
        l[j]//=2
    now*=2
print(*ret,sep=" ")

Measured memory_bytes: 96912
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    X = ir()
    c = {0:0}
    s = set([0])
    cnt = 1
    flag = True
    while flag:
        k = pow(cnt, 5)
        c[k] = cnt
        s.add(k)
        r = k-X
        if r in s:
            print(c[k], c[r])
            flag = False
            break
        if -r in s:
            print(c[k], -c[-r])
            flag = False
            break
        cnt += 1
resolve()

Measured memory_bytes: 61968
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = iss()
    S = []
    for i in range(1, 10):
        S += set(itertools.product('753', repeat=i))
    ret = 0
    for s in S:
        if '7' in s and '5' in s and '3' in s and int(N) >= int("".join(s)):
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 7788
#include <iostream>
using namespace std;
main(){
	int i,j,k,n; string s; cin>>n>>s;
	long long x=0,r=0,g=0,b=0;
	for(i=0;i<n;i++){
		s[i]=='R'?r++:s[i]=='G'?g++:b++;
		for (j=i+1,k=i+2;k<n;k+=2,j++)
			if((s[i]^s[j]^s[k])==('R'^'G'^'B'))x++;
	}
	cout<<r*g*b-x<<endl;
}

Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#define M 100000
using namespace std;
  
int main(){
    int n;
    int m;
    int l;
    int pos = 0;
    int ans = 0;
    int x[100010];
    scanf("%d %d",&n,&m);
    x[0] = 0;
    for (int i = 1; i < n; i++){
        scanf("%d", &x[i]);
        x[i] += x[i - 1];
    }
    while (m--){
        scanf("%d", &l);
        if(l > 0){
            ans += x[pos + l] - x[pos];
        }
        else{
            ans -= x[pos + l] - x[pos];
        }
        pos += l;
        ans %= M;
    }
    printf("%d\n", ans);
}

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

using namespace std;

string solve(const string &S)
{
	const int L = S.length();
	for (int i = 0; i < L; ++i) {
		for (int s = 0; i + s <= L; ++s) {
			string T = S;
			if (T.erase(i, s) == "keyence") {
				return "YES";
			}
		}
	}
	return "NO";
}

int main()
{
	string S;
	cin >> S;
	cout << solve(S) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
typedef long long ll;
using namespace std;

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i,0,n) {
        cin >> a[i];
    }
    map<int,int> m;
    ll ans=0;
    rep(i,0,n) {
        int li = i+a[i];
        m[li]++;
    }
    rep(i,0,n) {
        int rj = i-a[i];
        ans += m[rj];
    }
    cout << ans << endl;
}


Measured memory_bytes: 21128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=505,mod=998244353;
ll p[N];
int n,m,tot,vis[N],head[N],nex[N<<1],to[N<<1];
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
vector<ll>res[3];
void solve(int flag)
{
    tot=0;memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    priority_queue<int>q[2];
    int x=0,tim=0;
    for(int i=1;i<=n;i++) q[x].push(i);
    while(!q[x].empty())
    {
        tim++;
        ll ans=0;
        while(!q[x].empty())
        {
            while(!q[x].empty()&&vis[q[x].top()]==tim) q[x].pop();
            if(q[x].empty()) break;
            int u=q[x].top();q[x].pop();
            vis[u]=1e9;
            ans=(ans+p[u])%mod;
            for(int i=head[u];i;i=nex[i])
            {
                int v=to[i];
                if(vis[v]<tim)
                {
                    vis[v]=tim;
                    q[x^1].push(v);
                }
            }
        }
        x^=1;
        res[flag].push_back(ans);
    }
}
bool vis1[M][M],vis2[M];
ll solve()
{
    memset(vis2,0,sizeof(vis2));
    ll ans=0;
    for(int i=0;i<res[1].size();i++)
    {
        int mx=0;
        while(mx<res[2].size()&&vis1[i][mx]||vis2[mx]) mx++;
        if(mx<res[2].size())
        {
            vis1[i][mx]=vis2[mx]=true;
            ans=(ans+res[1][i]*res[2][mx])%mod;
        }
    }
    return ans;
}
int main()
{
    p[0]=1;
    for(int i=1;i<N;i++) p[i]=1000000000000000000ll%mod*p[i-1]%mod;
    scanf("%d",&n);
    solve(0);solve(1);solve(2);
    assert(res[0].size()<M);
    assert(res[1].size()<M);
    assert(res[2].size()<M);
    ll ans=0;
    for(int i=0;i<res[0].size();i++)
        ans=(ans+res[0][i]*solve())%mod;
    printf("%lld\n",ans);
}


Measured memory_bytes: 4336
import sys
input = sys.stdin.readline
from collections import *

S = input()[:-1]

if S=='SUN':
    print(7)
elif S=='MON':
    print(6)
elif S=='TUE':
    print(5)
elif S=='WED':
    print(4)
elif S=='THU':
    print(3)
elif S=='FRI':
    print(2)
elif S=='SAT':
    print(1)

Measured memory_bytes: 38256
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>
#include <iterator>


typedef long long ll;
typedef unsigned long long ull;
constexpr ll mop = 1000000007;
constexpr ll mop2 = 998244353;

using namespace std;

constexpr ll DEF_VAL = (1LL << 31) - 1;
constexpr ll SEG_LEN = (1LL << 17);

ll segTree[SEG_LEN * 2];

void initialize() {
	for (ll i = 0; i < SEG_LEN * 2; i++) {
		segTree[i] = DEF_VAL;
	}
}

void setVal(ll idx, ll val) {
	idx += SEG_LEN;
	segTree[idx] = val;
	while (true) {
		idx /= 2;
		if (idx <= 0) break;
		segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
	}
}

ll getMin(ll ql, ll qr, ll sl = 0, ll sr = SEG_LEN, ll idx = 1) {
	if (qr <= sl || sr <= ql) {
		return DEF_VAL;
	}
	if (ql <= sl && sr <= qr) {
		return segTree[idx];
	}
	ll sm = (sl + sr) / 2;
	ll m1 = getMin(ql, qr, sl, sm, 2 * idx);
	ll m2 = getMin(ql, qr, sm, sr, 2 * idx + 1);
	return min(m1, m2);

}

int main() {
	ll aLen, Q;
	cin >> aLen >> Q;
	initialize();
	for (ll i = 0; i < Q; i++) {
		ll com, l, r;
		cin >> com >> l >> r;
		if (com == 0) {
			setVal(l, r);
		}
		else {
			cout << getMin(l, r + 1) << endl;
		}
	}
}



Measured memory_bytes: 5148
#pragma region // {{{ by unolight
#include <bits/stdc++.h>
#include <unistd.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define RALL(x) rbegin(x),rend(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

namespace { namespace unolight {
// Read Input
template<class T> void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( int64_t &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<class T, class... U> void R( T& head, U&... tail ) { _R(head); R(tail...); }
// Write Output
template<class T> void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
void _W( const int64_t &x ) { printf("%" PRId64,x); }
void _W( const double &x ) { printf("%.16f\n",x); }
void _W( const char &x ) { putchar(x); }
void _W( const char *x ) { printf("%s",x); }
template<class T> void _W( const vector<T> &x ) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W( const T& head, const U&... tail ) { _W(head); putchar(sizeof...(tail)?' ':'\n'); W(tail...); }

#ifdef UNOLIGHT
#include "dump.hpp"
#else
#define dump(...)
#endif

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}
#pragma endregion // }}}

void main() {
    int a[4];
    REP(i,4) cin >> a[i];
    sort(a, a+4);
    int b[4]={1,4,7,9};
    REP(i,4) {
        if ( a[i] != b[i] ) {
            cout << "NO" << '\n';
            return;
        }
    }
    cout << "YES" << '\n';
}

}} // {{{ main
int main() { unolight::main(); return 0; }
// }}}

Measured memory_bytes: 3604
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main(void) {
    vector<int> A(3);
    vector<int> B(3);
    vector<int> C(3);

    for(int i=0;i<3;i++)cin>>A[i];
    for(int i=0;i<3;i++)cin>>B[i];
    for(int i=0;i<3;i++)cin>>C[i];

    int N;
    cin>>N;
    vector<int> D(N);
    for(int i=0;i<N;i++)cin>>D[i];

    for(int i=0;i<3;i++){
        for(int j=0;j<N;j++){
            if(A[i]==D[j]){
                A[i]=0;

                break;
            }

        }
    }

    for(int i=0;i<3;i++){
        for(int j=0;j<N;j++){
            if(B[i]==D[j]){
                B[i]=0;

                break;
            }
        }
    }

    for(int i=0;i<3;i++){
        for(int j=0;j<N;j++){
            if(C[i]==D[j]){
                C[i]=0;

                break;
            }
        }
    }



    if((C[0]==0&&C[1]==0&&C[2]==0)||(B[0]==0&&B[1]==0&&B[2]==0)||(A[0]==0&&A[1]==0&&A[2]==0)||(A[0]==0&&B[0]==0&&C[0]==0)||(A[1]==0&&B[1]==0&&C[1]==0)||(A[2]==0&&B[2]==0&&C[2]==0)||(A[0]==0&&B[1]==0&&C[2]==0)||(A[2]==0&&B[1]==0&&C[0]==0)){

        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }


}


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

int dfs(int now, int depth, vector<vector<int> >& adjlist, vector<bool>& used){
  used[now] = true;
  if(depth <= 0){ return 1; }
  int count = 1;
  for(int i = 0; i < (int)adjlist[now].size(); i++){
    if(!used[adjlist[now][i]]){
      count += dfs(adjlist[now][i], depth - 1, adjlist, used);
    }
  }
  return count;
}

int main(void){
  int n, k;
  cin >> n >> k;

  int a, b;
  vector<vector<int> > adjlist(n);
  vector<pair<int, int> > edge;
  for(int i = 0; i < n - 1; i++){
    cin >> a >> b;
    --a;
    --b;
    adjlist[a].push_back(b);
    adjlist[b].push_back(a);
    edge.push_back(make_pair(a, b));
  }

  int ans = 0;
  if(k % 2 == 0){
    for(int i = 0; i < n; i++){
      vector<bool> used(n, false);
      ans = max(ans, dfs(i, k / 2, adjlist, used));
    }
  }
  else{
    for(int i = 0; i < n - 1; i++){
      vector<bool> used(n, false);
      used[edge[i].first] = used[edge[i].second] = true;
      ans = max(ans, dfs(edge[i].first, k / 2, adjlist, used)
                + dfs(edge[i].second, k / 2, adjlist, used));
    }
  }

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


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;

vector<ull> P, length;

ull solve(ull x, int level)
{
    if(x==1)
    {
        return 0;
    }
    if (level == 1)
    {
        return min((ull)3, x - 1);
    }
    if (x <= length[level] / 2)
    {
        return solve(x - 1, level - 1);
    }
    else if (x == length[level] / 2 + 1)
    {
        return P[level-1] + 1;
    }
    else
    {
        return solve(x - length[level - 1] - 2, level - 1) + P[level - 1] + 1;
    }
}

int main()
{
    ull N, X;

    cin >> N >> X;
    ull ans = (ull)0;
    P.resize(N + 1);
    length.resize(N + 1);
    //  vector<vector<ull>> dp(51, vector<ull>(X + 1));
    P[0] = 1;
    length[0] = 1;
    rep(i, N)
    {
        P[i + 1] = 2 * P[i] + 1;
        length[i + 1] = 2 * length[i] + 3;
    }
    /*rep(i,N)
    {
        ull tmp = 0;
        if(X<=length[i+1]/2)
        {
            tmp = dp[i][X];
        }
        else if (X == length[i + 1] / 2+1)
        {
            tmp = dp[i][X] + 1;
        }
        dp[i + 1][X] =
    }*/
    /*   for (int i = N; i > 0;i--)
    {
        if(X<i)
        {
            break;
        }
        X -= i;
        ans += min(X, P[i-1]);
        X -= min(X, P[i - 1]);
        if (X < i)
        {
            break;
        }
        X -= i;
    }
    */
    cout << solve(X, N);
    return 0;
}

Measured memory_bytes: 256
# after listening explanation

s = gets.chomp.chars.map(&:to_i)
sn = s.size
@mod = 2019

mods = []
mod_now = 1
sn.times{
  mod_now *= 10
  mod_now %= @mod
  mods << mod_now
}
cumula = [0]
sn.times{|i|
  cumula << ((cumula.last + s[i] * mods[sn-i-1])  % @mod)
}
cumula_dup = []
cumula.group_by(&:itself).each{ |key, value|
  c = value.count
  (cumula_dup << c) if c>1
}
p cumula_dup.map{|c| c*(c-1)/2 }.sum


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

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

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

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

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

    cin>>n>>m;
    rep(i,n)cin>>a[i];
    rep(i,m)cin>>b[i],sum+=b[i];
    rep(i,n){
            ans+=a[i]*sum;
    }
    Cout(ans);
    return 0;
}



Measured memory_bytes: 4780
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>
#include <sstream>
#include <set>

const long long MOD = 1000000007;
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

int main(){
    llong N,M;
    cin >> N >> M;
    vector<llong> A(N);
    priority_queue<llong> PQ;

    for(int i=0; i<N; i++){
        cin >> A[i];
        PQ.push(A[i]);
    }
    llong total = 0;
    llong temp;
    for(int i=0; i<M; i++){
        //最大値を探す
        temp = PQ.top();
        PQ.pop();
        PQ.push(temp/2);
    }
    for(int i=0; i<N; i++){
        total = PQ.top() + total;
        PQ.pop();
    }
    cout << total << endl;
    return 0;
}


Measured memory_bytes: 4580
import java.util.*;

public class Main {

	private static List<Integer> getStrings(Scanner sc, int num) {
		List<Integer> stringList = new ArrayList<>();
		while(num>0) {
			int nextInt = sc.nextInt();
			stringList.add(nextInt);
			num--;
		}
		return stringList;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Integer> array = getStrings(sc, n);
		array.sort(Integer::compareTo);
		int[] result = new int[1000001];
		int max = array.get(array.size()-1);
		int count = 0;
		for (int i = 0; i < array.size(); i++) {
			int m = array.get(i);
			if (result[m] == 0) {
				for (int j = m; j <= max; j+=m) {
					result[j]++;
				}
			} else {
				result[m]++;
			}
		}
		for (int i = 0; i < array.size(); i++) {
			if (result[array.get(i)] == 1) {
				count++;
			}
		}
		System.out.println(count);
		return;
	}

}


Measured memory_bytes: 64816
#include<stdio.h>
#include<string.h>
#pragma warning(disable:4996)
int main()
{
	char a[51], b[51];
	scanf("%s", a);
	scanf("%s", b);
	int u = 0;
	for (int i = 0; i < strlen(a); i++)
	{
		int count = 0;
		for (int j = 0; j < strlen(b); j++)
		{
			if (a[i + j] == b[j] || a[i + j] == '?')
			{
				count++;
			}
		}
		if (count == strlen(b))
		{
			u = i+1;
		}
	}
	if (u==0)
	{
		printf("UNRESTORABLE");
	}
	else
	{
		for (int i = 0; i < u-1; i++)
		{
			if (a[i]=='?')
			{
				a[i] = 'a';
			}
		}
		for (int i = u-1; i < u-1+strlen(b); i++)
		{
			a[i] = b[i + 1 - u];
		}
		for (int i = u - 1 + strlen(b); i < strlen(a); i++)
		{
			if (a[i] == '?')
			{
				a[i] = 'a';
			}
		}
		printf("%s", a);
	}
	return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b){
  if (a < b){
    a = b;
    return true;
  }
  return false;
}

int main(){
  cout << fixed << setprecision(15);
  
  int a; cin >> a;

  //ll ans = 0;
  string ans = "No";
  rep(i, 9)
    rep(j, 9)
      if ((i + 1) * (j + 1) == a) ans = "Yes";
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
 
ll wt[105] , Val[105];
 
int main()
{   
    int N ;
    ll W;
    cin >> N >> W;
 
    ll sum =0;
    for(int i=1; i<=N; i++)
    {
        cin >> wt[i] >> Val[i];
        sum += Val[i];
    } 
 
    ll dp[sum+1];
 
        for(int j=0; j<=N;j++)
    {
    for(ll i =0; i<=sum; i++)        {
            if(i==0) dp[i] = 0;
            else
            {
                dp[i] = 1000000000000LL;
                
            }
        }
    }
    
        for(int j=1; j<=N; j++)
        {
            for(ll s=sum; s>=0 ; s--)
            {
            if(s >=Val[j])
                dp[s] = min(dp[s], dp[s-Val[j]]+wt[j]);
            // cout<< dp[s][j]<< endl;
        }
        
    }
    // ll result;
    for(ll s=sum; s>0; s--){
        if(dp[s] <=W){
            cout << s <<endl;
            break;
        }
    }
    // cout << INT64_MAX;
    return 0;
}

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

#define REP(i,j) for(int i=0;i<j;i++)
#define REPR(i,j) for(int i=j;i>=0;i--)
#define FOR(i,j,k) for(int i=j;i<k;i++)

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

    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if(A+B > C+D){
        cout << "Left\n";
    }else if(A+B < C+D){
        cout << "Right\n";
    }else{
        cout << "Balanced\n";
    }
    return 0;
}

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

int main(){
   int N, M;
   std::cin >> N;
   std::vector<std::string> s(N);
   for(int i=0; i<N; ++i)
      std::cin >> s[i];

   std::cin >> M;
   std::vector<std::string> t(M);
   for(int i=0; i<M; ++i)
      std::cin >> t[i];

   int max = 0;
   for(int i=0; i<N; ++i){
      int count = 1;
      for(int j=i+1; j<N; ++j){
	 if(s[i]==s[j]) ++count;
      }
      for(int j=0; j<M; ++j){
	 if(s[i]==t[j]) --count;	 
      }
      if(max<count) max = count;
   }
   std::cout << max << std::endl;
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int ans=0;
	for(int i=1;i<n;i++){
		int cnt=0;
		for(char c='a';c<='z';c++){
			bool left=false,right=false;
			for(int j=0;j<i;j++)
				if(s[j]==c){
					left=true;
					break;
				}
			for(int j=i;j<n;j++)
				if(s[j]==c){
					right=true;
					break;
				}
			if(left&&right)
				cnt++;
		}
		if(ans<cnt)
			ans=cnt;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long
vector<int> fact(int m){
  vector<int> resl(1,1),resh(1,m);
  if(m==1)return resl;
  for(int i=2;i*i<=m;++i){
    if(m%i==0){
      resl.push_back(i);
      if(i!=m/i&&m%(m/i)==0)resh.push_back(m/i);
    }
  }
  for(auto it=resh.rbegin();it!=resh.rend();++it)resl.push_back(*it);
  return resl;
}
main(){
  int n,r=0;
  cin>>n;
  vector<int> f(fact(n)),g(fact(n-1));
  for(auto p:g)if(p>1&&n%p==1)++r;
  for(auto p:f){
    if(p==1)continue;
    int m=n;
    while(m&&m%p==0)m/=p;
    if(m%p==1)++r;
  }
  cout<<r;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const ll LINF = 1LL<<60;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }

    int x, n; cin >> x >> n;
    set<int> pa;
    for (int i = 0; i < n; i++) {
        int z; cin >> z; pa.insert(z);
    }
    int mind = INF;
    int ans = INF;
    for (int p = -200; p <= 200; p++) {
        if (pa.count(p)) continue;
        if (abs(x-p) < mind) {
            mind = abs(x-p);
            ans = p;
        } else if (abs(x-p) == mind) {
            ans = min(ans, p);
        }
    }
    cout << ans << endl;

    return 0;
}

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

// isDebug?
#ifndef ONLINE_JUDGE
#define _DEBUG
#endif

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// -* https://xn--kst.jp/blog/2019/08/29/cpp-comp/ *- Thx :)
// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    cout << __FILE__ << ": " << __LINE__ << ": " << __func__ << " -> ";   \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

// namespace / type / class / struct - alias, def:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;
const int FACN = 510000;

// Global Variables:
// ll fac[FACN], finv[FACN], inv[FACN];

// Prototype Declarations:
int gcd(int, int);
int lcm(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int x;
    cin >> x;
    x /= 200;
    cout << 10 - x << endl;
    return 0;
}
// ===========================================

// Functions:
// 最大公約数 O(log(min(a, b)))
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
// 最小公倍数 O(log(min(a, b)))
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

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

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


Measured memory_bytes: 3592
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, k, v[100];
string str;

int main(){
	cin >> n >> k;
	for(ll i = 1; i <= n; i++){cin >> v[i];}
	
	ll ans = 0;
	for(ll l = 0; l <= min(k, n); l++){
		for(ll r = 0; r <= min(k-l, n-l); r++){
			priority_queue<ll, vector<ll>, greater<ll>> q;
            for(ll li = 1; li <= l; li++){q.push(v[li]);}
            for(ll ri = 1; ri <= r; ri++){q.push(v[n+1-ri]);}
			for(ll ki = 1; ki <= k-l-r && !q.empty(); ki++){if(q.top() < 0){q.pop();}}
			ll ansbuf = 0;
			while(!q.empty()){
				ansbuf += q.top();
				q.pop();
			}
			//cout << ansbuf << endl;
			ans = max(ansbuf, ans);
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

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

d = defaultdict(int)
for v in a:
    d[v] += 1

max_ans = 0
for k, v in d.items():
    max_ans += v * (v-1) // 2

ans = []
for v in a:
    if d[v] > 1:
        ans.append(max_ans - ((d[v]) * (d[v]-1) // 2) + ((d[v]-1) * (d[v]-2) // 2))
    else:
        ans.append(max_ans)

print("\n".join(list(map(str, ans))))

Measured memory_bytes: 113484
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

struct UnionFind {
  vector<int> parent;  // parent[root] is the negative of the size.
  UnionFind(int n)
      : parent(n, -1){};
  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (parent[u] > parent[v]) swap(u, v);
    parent[u] += parent[v];
    parent[v] = u;
    return true;
  }
  bool find(int u, int v) {
    return root(u) == root(v);
  }
  int root(int u) {
    return parent[u] < 0 ? u : parent[u] = root(parent[u]);
  }
  int size(int u) {
    return -parent[root(u)];
  }
};

bool solve(const vector<ll>& A, const vector<ll>& B) {
  int N = A.size();
  vector<int> a_id(N), b_id(N);
  iota(a_id.begin(), a_id.end(), 0);
  iota(b_id.begin(), b_id.end(), 0);
  sort(a_id.begin(), a_id.end(), [&](int a, int b) {
    if (A[a] != A[b]) return A[a] < A[b];
    return a < b;
  });
  sort(b_id.begin(), b_id.end(), [&](int a, int b) {
    if (B[a] != B[b]) return B[a] < B[b];
    return a < b;
  });
  for (int i = 0; i < N; i++) {
    if (A[a_id[i]] > B[b_id[i]]) return false;
  }
  UnionFind uf(N);
  for (int i = 0; i < N; i++) uf.unite(a_id[i], b_id[i]);
  set<int> S;
  for (int i = 0; i < N; i++) S.insert(uf.root(i));
  if (S.size() > 1) return true;
  for (int i = 0; i + 1 < N; i++) {
    int a1 = a_id[i], a2 = a_id[i + 1];
    int b1 = b_id[i], b2 = b_id[i + 1];
    if (A[a2] <= B[b1] && A[a1] <= B[b2]) {
      return true;
    }
  }
  return false;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vector<ll> A(N), B(N);
    for (ll& x : A) cin >> x;
    for (ll& x : B) cin >> x;
    cout << (solve(A, B) ? "Yes" : "No") << endl;
  }
  return 0;
}


Measured memory_bytes: 2944
/*input
4
3 4 3 2
*/

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

#define mx 100005
#define ll long long
#define MOD 1000000007
#define fs first
#define sc second


int main()
{
	int n;
	scanf("%d", &n);
	ll ara[n];
	for(int i = 0; i<n; i++)
		scanf("%lld", &ara[i]);
	ll l = 2, r = 2, f = 0;
	for(int i = n-1; i>=0; i--)
	{
		ll a = (l + ara[i] - 1)/ara[i] * ara[i];
		ll b = r/ara[i] * ara[i];
		if(!(l <= a && a <= r && l <=b && b <= r && a <= b)) f = 1;
		l = a;
		r = b + ara[i] - 1;
	}
	if(f) printf("-1\n");
	else printf("%lld %lld\n", l, r);
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <map>
#include <sstream>
#include <algorithm>
using namespace std;
#define sz(c) int((c).size())

int main(int argc, char **argv)
{
  string s;
  int corp, date;
  char c;
  map<int, int> m, n;
  while (getline(cin, s)) {
    if (sz(s) == 0)
      break;
    istringstream is(s);
    is >> corp >> c >> date;
    m[corp]++;
  }
  while (cin >> corp >> c >> date) {
    n[corp]++;
  }
  for (auto& p : m) {
    if (n[p.first])
      cout << p.first << " " << n[p.first] + p.second << endl;
  }
  return 0;
}

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

using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using f64 = double;
using f80 = long double;

#define FOR(v, a, b) for(i64 v = (a); v < (b); ++v)
#define FORE(v, a, b) for(i64 v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(i64 v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

using namespace std;

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T> void pout(const T &value){std::cout << value << "\n";}
template <typename T, typename ...Args> void pout(const T &value, const Args&... args){std::cout << value << " ";pout(args...);}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <typename T> auto make_vector(int n, int m, const T &value){return vector<vector<T>>(n, vector<T>(m, value));}


struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;



int main(){
  int K;
  while(cin >> K){

    queue<i64> q;
    FORE(i,1,9) q.push(i);

    int c = 0;
    while(q.size()){
      i64 x = q.front(); q.pop();

      ++c;

      if(c == K){
        pout(x);

        break;
      }

      i64 l = x % 10;


      FORE(i,-1,1){
        if(l + i >= 0 and l + i <= 9)
          q.push(x * 10 + (l + i));
      }
    }

    
  }
  
  return 0;
}


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

int main() {
  int a,b=0;
  cin >> a;
  b += a%10;
  a /= 10;
  b += a%10;
  a /= 10;
  b += a % 10;
  cout << b << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#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>
#include <unordered_map>
#include <iomanip>
//#pragma GCC optimize("Ofast")
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
//#define int ll
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 pair<int,int> pii;
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(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#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 floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
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 / 2;
const ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  int N, M;
  cin >> N >> M;
  vpii ba(M);
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    ba[i] = make_pair(b, a);
  }
  sort(all(ba));
  
  //貪欲
  int prevRemoved = -1;
  int removeCount = 0;
  rep(i, M) {
    int a = ba[i].second;
    int b = ba[i].first;
    
    if(prevRemoved >= a && prevRemoved < b) {
      //既に取り除いた => 何もしない      
    } else {
      //まだ => 取り除く
      prevRemoved = b - 1;
      removeCount ++;
    }
  }
  
  fin(removeCount);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort( ALL(v) )

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

int main()
{



    int n; cin>>n;
    vector<P> v(n);
    map<int,int> cnt;
    for(int i = 0 ; i<n ; i++)
    {
        int x;
        cin >> x;
        v[i] = {x,i};
    }
    sort(v.begin() , v.end());
    int curMed = (n-1)/2;
    vector<int> ans(n);
    for(int i = 0 ; i<n ; i++)
    {
        int idx = v[i].second;
        if(i==0)
        {
            int x = v[curMed+1].first;
            ans[idx] = x;
        }
        else if(i>curMed)
        {
                int x = v[curMed].first;
                ans[idx] = x;
        }
        else if(i<=curMed)
        {
            ans[idx] = v[curMed+1].first;
        }

        else if(i==n-1)
        {
            ans[idx] = v[curMed+1].first;
        }
    }

    for(auto x : ans)
        cout<<x<<endl;



    return 0;
}


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

#define int long long
#define endl '\n'
#define sp << " "
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

int dp[3005][3005];
int n, m;
string s, t;
int lcs(int i, int j)
{
    if(i >= n || j >= m)
        return 0;
    if(dp[i][j] != -1) 
        return dp[i][j];
    int ans = 0;
    if(s[i] == t[j])
        ans = 1 + lcs(i + 1, j + 1);
    else
    {
        ans = max(lcs(i + 1, j), lcs(i, j + 1));
    }
    return dp[i][j] = ans;

}
void print(int i, int j)
{
    if(i >= n || j >= m)
        return;
    int ans = dp[i][j];
    if(s[i] == t[j])
    {
        cout << s[i];
        print(i + 1, j + 1);
        return;
    }
    else
    {
        if(ans == dp[i + 1][j])
        {
            return print(i + 1, j);
        }
        else 
            return print(i, j + 1);
    }
    
}
int32_t main()
{
    ios

    cin >> s >> t;
    n = s.size();
    m = t.size();
    memset(dp, -1, sizeof(dp));
    int mx = lcs(0, 0);
    // for(int i = 0; i < n; i++)
    // {
    //     for(int j = 0; j < m; j++)
    //         cout << dp[i][j] << " ";
    //     cout << endl;
    // }
    print(0, 0);
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 71168
#include <iostream>
#include <cmath>
#include <iomanip>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

long long gcd(int x, int y){
    if ( x == 0 ) return y;

    return gcd(y%x, x);
}

long long lcm(int x, int y){
    if ( y == 0 ){
        return x;
    }

    return x*y/gcd(x, y);
}

int min(int a, int b){
    return a > b ? b : a;
}

int max(int a, int b){
    return a > b ? a : b;
}

int n;
vector <int> tree(400005, 0);

int query(int a){
    int res = 0;
    for (;a>0;a-=a&-a){
        res+=tree[a];
    }

    return res;
}

void update(int a){
    for (;a<=200000;a+=a&-a){
        tree[a]++;
    }
}

int main()
{
    cin.sync_with_stdio( false );
    cin>>n;

    int res = 0;
    for (int i=0;i<n;i++){
        int a;
        cin>>a;

        if ( i == 0 ){
            update(a);
            res++;
        }else{
            update(a);
            if ( query(a) - 1 == 0 ){
                res++;
            }
        }
    }

    cout<<res<<endl;
}


Measured memory_bytes: 4644
from functools import lru_cache
cc = [["." for i in range(8)] for j in range(8)]
 
def check(cc,a,b):
    ss = list(zip(*cc))
    if 'Q' in cc[a]: return False
    if 'Q' in ss[b]: return False
    d = []
    for i in range(8):
        for j in range(8):
            try:
                if j + abs(a - i) == b: 
                    d.append(cc[i][j])
                if j -  abs(a - i) == b:
                    d.append(cc[i][j])
            except IndexError: continue
    if 'Q' in d: return False
    return True
 
def chess(s, queen):
    if queen == 8:
        return s
    for i in range(8):
        for j in range(8):
            if check(s, i, j):
                sol = s
                sol[i][j] = 'Q'
                if chess(sol, queen+1) != [[]]:
                    return sol
                else: sol[i][j] = "."
    return [[]]
 
 
k = int(input())
for i in range(k):
    a, b = map(lambda x: int(x), input().split())
    cc[a][b] = 'Q'
ans = chess(cc, k)
print('\n'.join(list(map(lambda x: ''.join(x), ans))) )



Measured memory_bytes: 6300
#include <iostream>
#include <climits>
#include <vector>

int min(int x, int y)
{
	return x>y ? y : x;
}

void stable_merge(int* perm, int *A, int left, int mid, int right)
{
	int n1 = mid - left;
	int n2 = right - mid;
	int* L = new int[n1+1];
	int* R = new int[n2+1];
	int* Lperm = new int[n1];
	int* Rperm = new int[n2];
	for (int i=left; i<mid; i++) {
		L[i-left] = A[i]; Lperm[i-left] = perm[i];
	}
	for (int i=mid; i<right; i++) {
		R[i-mid] = A[i]; Rperm[i-mid] = perm[i];
	}
	L[n1] = R[n2] = INT_MAX;
	int l = 0, r = 0;
	for (int k=left; k<right; k++) {
		if (L[l] > R[r]) {
			A[k] = R[r]; perm[k] = Rperm[r]; 
			r++;
		} else {
			A[k] = L[l]; perm[k] = Lperm[l];
			l++;
		}
	}
	delete[] L;
	delete[] R;
	delete[] Lperm;
	delete[] Rperm;
}

void stable_mergeSort(int* perm, int *A, int left, int right)
{
	if (left+1 < right) {
		int mid = (left + right) / 2;
		stable_mergeSort(perm, A, left, mid);
		stable_mergeSort(perm, A, mid, right);
		stable_merge(perm, A, left, mid, right);
	}
}


int main()
{
	int n;
	std::cin >> n;
	
	int* w = new int[n];
	for (int i=0; i<n; i++) std::cin >> w[i];
	
	int* perm = new int[n];
	for (int i=0; i<n; i++) perm[i] = i;
		
	stable_mergeSort(perm, w, 0, n);
	
	bool* visited = new bool[n];
	for (int i=0; i<n; i++) visited[i] = false;
	
	int total_cost = 0;
	for (int i=0; i<n; i++) {
		if (visited[i]) continue;
		if (i == perm[i]) continue;
		std::vector<int> cycle;
		int k = i;
		do {
			cycle.push_back(k);
			visited[k] = true;
			k = perm[k];
		} while (!visited[k]);
		int cost_of_cycle = min( (cycle.size()-1) * w[i], 2 * w[i] + (cycle.size()+1) * w[0]);
		for (int j=1; j<cycle.size(); j++) {
			cost_of_cycle += w[cycle[j]];
		}
		total_cost += cost_of_cycle;
	}
	
	std::cout << total_cost << std::endl;
	
	delete[] w;
	delete[] perm;
	delete[] visited;
	
	return 0;
}




Measured memory_bytes: 3176
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    vector<pll> AB(M);
    for(int i = 0; i < M;i++){
        cin >> AB[i].first >> AB[i].second;
    }
    sort(AB.begin(),AB.end());
    reverse(AB.begin(), AB.end());
    ll res = 0;
    for(int i = 0; i < M-1;i++){
        if(AB[i].first >= N)continue;
        else{
            res += N - AB[i].first;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3188
#include "bits/stdc++.h"
using namespace std;

int main() {
	
	int n;
	cin >> n;
	int gr[2][n];
	for (int i=0; i<2; i++) for (int j=0; j<n; j++) cin >> gr[i][j];
	
	int best[2][n];
	best[0][0] = gr[0][0];
	for (int i=1; i<n; i++) {
		best[0][i] = best[0][i-1] + gr[0][i];
	}
	best[1][0] = gr[0][0] + gr[1][0];
	for (int i=1; i<n; i++) {
		best[1][i] = max(best[0][i], best[1][i-1]) + gr[1][i];
	}
	
	cout << best[1][n-1] << endl;
	
}


Measured memory_bytes: 256