akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << #x << ':' << x << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

const int N = 100010;
vector<vector<P>> graph(N, vector<P>());
vector<ll> sz(N, 1);
vector<int> center;
ll ans;

void dfs1(int n, int p, int tr) {
	bool flag = true;
	for (P i : graph[n]) {
		int v = i.first;
		if (v == p) continue;
		dfs1(v, n, tr);
		sz[n] += sz[v];
		if (sz[v] > tr / 2) flag = false;
	}
	if (flag && sz[n] >= (tr + 1) / 2) center.pb(n);
}

vector<ll> nsz(N, 1);

void dfs2(int n, int p) {
	for (P i : graph[n]) {
		int v = i.first;
		if (v == p) continue;
		dfs2(v, n);
		nsz[n] += nsz[v];
	}
}

void dfs3(int n, int p) {
	for (P i : graph[n]) {
		int v = i.first; ll cost = i.second;
		if (v == p) continue;
		ans += cost * nsz[v] * 2;
		dfs3(v, n);
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n;
	cin >> n;
	rep(i, n - 1) {
		ll u, v, c;
		cin >> u >> v >> c;
		u--; v--;
		graph[u].pb({ v,c });
		graph[v].pb({ u,c });
	}
	dfs1(0, -1, n);
	if (center.size() == 1) {
		dfs2(center[0], -1);
		dfs3(center[0], -1);
		ll mi = inf;
		for (P p : graph[center[0]]) chmin(mi, p.second);
		cout << ans - mi << '\n';
	}
	else {
		dfs2(center[0], center[1]); dfs3(center[0], center[1]);
		dfs2(center[1], center[0]); dfs3(center[1], center[0]);
		for (P p : graph[center[0]]) if (p.first == center[1]) ans += (n - 1) * p.second;
		cout << ans << '\n';
	}
}

Measured memory_bytes: 20188
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Q = lr()
graph = np.array([[0] * (N+1) for _ in range(N+1)])  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

for i in range(N+1):
    graph[i] = graph[i].cumsum()

graph = np.cumsum(graph, axis=0)
for _ in range(Q):
    p, q = lr()
    answer = graph[q][q] - graph[q][p-1] - graph[p-1][q] + graph[p-1][p-1]
    print(answer)

# 30


Measured memory_bytes: 16556
#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 3005, mod = 998244353;
int a, c, b, d;
ll mem[MX][MX];

ll dp (int a, int b) {
	if (a > c || b > d) return 0;
	if (a == c && b == d) return 1;

	ll &res = mem[a][b];
	if (res != -1) return res;
	res = 0;

	res += a * dp(a, b + 1);
	res += b * dp(a + 1, b);
	res -= a * b % mod * dp(a + 1, b + 1);

	return res %= mod;
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> a >> b >> c >> d;
	memset(mem, -1, sizeof(mem));
	cout << MOD(dp(a, b), mod) << endl;

	return 0;
}


Measured memory_bytes: 74592
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

const long long INF = 1LL << 60;

int main()
{
    int k;
    cin >> k;
    int ans = k % 2 == 0 ? k * k / 4 : ((k + 1) / 2) * (k / 2);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3584
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
using namespace std;
#define N 1010
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,vis[N],ok;
int ans[N],an,ins[N],G[N][N];
vector<int> st;
int head[N],cnt=0;
struct Edge{
	int to,nxt;
}edge[N<<1];
void add(int a,int b){
	cnt++;
	edge[cnt].to=b;
	edge[cnt].nxt=head[a];
	head[a]=cnt;
}
void dfs(int u){
	if(ok)return;
	//yet[u]=1;
	for(int i=st.size()-1;!ok&&i>=0;i--){
		int v=st[i];
		if(G[u][v]){
			cout<<st.size()-i<<endl;
			for(int j=i;j<st.size();j++){
				cout<<st[j]<<endl;
			}
			exit(0);
		}
	}
	int g=0,go[1001]={};
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(!vis[v]){
			go[++g]=v;
		}
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		vis[v]=1;
	}
	for(int i=1;i<=g;i++){
		st.push_back(go[i]);
		dfs(go[i]);
		st.pop_back();
	} 
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		vis[v]=0;
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		add(u,v);
		G[u][v]=1;
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		memset(ins,0,sizeof(ins));
		dfs(i);
	}
	if(!ok){
		cout<<-1<<endl;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 7552
gets.to_i
kekka=gets.chomp.split(" ").map(&:to_i)
m=gets.to_i
m.times{
  p,x=gets.chomp.split(" ").map(&:to_i)
  puts kekka.inject(:+) - kekka[p-1] + x
  #kekka_dup=kekka.dup
  #kekka_dup[p-1]=x
  #puts kekka_dup.sum
}

Measured memory_bytes: 1788
n, k = map(int, input().split())
r, s, p = map(int, input().split())
add = [p, r, s]
rsp_str = ['r', 's', 'p']
t = input()
box = [None]*k
points = [None]*k

for i in range(k):
    box[i] = [rsp_str.index(str) for str in t[i::k]]

for i in range(k):
    prev = -1
    point = 0
    for hand in box[i]:
        if hand == prev:
            prev = -1
            continue
        point += add[hand]
        prev = hand
    points[i] = point

print(sum(points))


Measured memory_bytes: 17012
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mp make_pair
typedef long long ll;
using namespace std;
const int maxn=100010;
int nd[maxn<<1],nex[maxn<<1],lnk[maxn],e,n,sg[maxn];
void add(int u,int v){
	nd[++e]=v;nex[e]=lnk[u];lnk[u]=e;
}
void dfs(int u,int fa){
	sg[u]=0;
	for (int i=lnk[u]; i;i=nex[i]){
		if (nd[i]==fa) continue;
		dfs(nd[i],u);
		sg[u]^=sg[nd[i]]+1;
	}
}
int main(){
	scanf("%d",&n);
	for (int i=1,u,v; i<n; i++){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	printf(sg[1]?"Alice":"Bob");
	return 0;
}

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

int main(){//ACGT以外の位置を出して引き算で求めたい←これだと全部ACGTの時対応できない
    string s;cin>>s;
    int n=s.size();vector<int> l(15);int k=0,ans=0;//l={0,...}k個のACGT以外の文字
    for(int i=0;i<n;i++){
        if(s.at(i)!='A'&&s.at(i)!='C'&&s.at(i)!='G'&&s.at(i)!='T'){
            k++;
            l.at(k)=i;
        }
    }
    l.at(k+1)=n-1;
    ans=max(l.at(1)-l.at(0),l.at(k+1)-l.at(k));//
    for(int i=0;i<=k;i++){
        ans=max(l.at(i+1)-l.at(i)-1,ans);
    }
    if(k!=0) cout<<ans<<endl;
    else cout<<n<<endl;
}

Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQUE(c)   sort(ALL((c)));(c).erase(unique(ALL((c))),(c).end())
# define LOWER(s)    transform(ALL((s)),(s).begin(),TL<char>)
# define UPPER(s)    transform(ALL((s)),(s).begin(),TU<char>)
# define FOR(i,a,b)  for(LL i=(a);i<(b);i++)
# define RFOR(i,a,b) for(LL i=(a);i>=(b);i--)
# define REP(i,n)    FOR(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int N, M, C, S, G;
int dis[32][128][128], p[32], q[32][64], r[32][64];
int fare[32][20010], cost[128][128];

int main() {
	while (cin >> N >> M >> C >> S >> G && (N||M||C||S||G)) {
		S--; G--;
		REP(c, C)REP(i, N)REP(j, N) dis[c][i][j] = HINF;
		REP(i, M) {
			int x, y, d, c;
			cin >> x >> y >> d >> c;
			x--, y--, c--;
			dis[c][x][y] = dis[c][y][x] = min(dis[c][x][y], d);
		}
		REP(c, C) cin >> p[c];
		REP(c, C) {
			REP(i, p[c] - 1) cin >> q[c][i];
			REP(i, p[c]) cin >> r[c][i];
		}
		REP(c, C)REP(k, N)REP(i, N)REP(j, N) {
			dis[c][i][j] = min(dis[c][i][j], dis[c][i][k] + dis[c][k][j]);
		}
		REP(c, C) {
			int num = 0; fare[c][0] = 0;
			REP(i, 20000) {
				if (num < p[c] - 1 && i == q[c][num]) num++;
				fare[c][i + 1] = fare[c][i] + r[c][num];
			}
		}
		REP(i, N)REP(j, N) cost[i][j] = HINF;
		REP(c, C)REP(i, N)REP(j, N) if (dis[c][i][j] < HINF) cost[i][j] = min(cost[i][j], fare[c][dis[c][i][j]]);
		REP(k, N)REP(i, N)REP(j, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
		cout << (cost[S][G] == HINF ? -1 : cost[S][G]) << endl;
	}
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
typedef pair<int,string>XXX;
#define F first
#define S second

string def(int x){
    string t;
    while(x)t+=(x%10)+'0',x/=10;
    reverse(t.begin(),t.end());
    while(t.size()!=6)t='0'+t;
    return t;
}

signed main(){
    map<int,int>M;
    int n,m;
    cin>>n>>m;
    vector<P2>v;
    r(i,m){
        int a,b;
        cin>>a>>b;
        v.push_back(P2(b,P(a,i)));
    }
    sort(v.begin(),v.end());
    vector<XXX>g;
    r(i,m){
        string s;
        s=def(v[i].S.F);
        int y=v[i].S.F;
        M[y]++;
        s+=def(M[y]);
        g.push_back(XXX(v[i].S.S,s));
    }
    sort(g.begin(),g.end());
    r(i,m){
        cout<<g[i].S<<endl;
    }
}

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

using namespace std;

int main()
{
    int n, p;
    
    while (scanf("%d %d", &n, &p) && n){
        int a = p, b[50] = {0}, c = 0;
        while (1){
            if (a){
                b[c]++;
                a--;
            }
            else {
                a += b[c];
                b[c] = 0;
            }
            if (b[c] == p){
                printf("%d\n", c);
                break;
            }
            c = (c + 1) % n;
        }
    }
    return (0);
}

Measured memory_bytes: 1188
/**********************************************
 * author : deepak nayan
 * file   : e:/Solutions/atcoder/abc072_a.cpp
 * time   : Tue Apr 28 23:40:54 2020
 * quest  : A - Sandglass2
 *********************************************/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int x, t;
  cin >> x >> t;
  cout << ((x - t) > 0 ? (x - t) : 0) << "\n";
  return 0;
}


Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
constexpr int D=365;
constexpr int beam = 260;
int c[26];
int s[D][26];
int ans[D];

struct State{
    int val = 0;
    int out[D]={0};
    int cnt[26]={0};
};

constexpr bool operator< (const State &a, const State &b){
    return a.val<b.val;
}
constexpr bool operator> (const State &a, const State &b){
    return a.val>b.val;
}


void solve(int ca){
    int waste;
    scanf("%d",&waste);
    for (int i = 0; i < 26; ++i) {
        scanf("%d",c+i);
    }
    for (auto & i : s) {
        for (int & j : i) {
            scanf("%d",&j);
        }
    }

    priority_queue<State> pq[2];
    pq[0].push(State());
    for (int i = 0; i < D; ++i) {
        int prev=i&1,next = prev^1;
        for (int j = 0; !pq[prev].empty()&&j < beam; ++j) {
            auto state = pq[prev].top();
            pq[prev].pop();
            int dec=0;
            for (int k = 0; k < 26; ++k) { 
                state.cnt[k]++;
                dec+=c[k]*state.cnt[k];
            }
            for (int k = 0; k < 26; ++k) {
                const int inc = c[k]*state.cnt[k];
                const int tmp = state.cnt[k];
                const int tmp_val = state.val;
                state.val = state.val-dec+inc+s[i][k];
                state.cnt[k]=0;
                state.out[i]=k;
                pq[next].push(state);
                state.cnt[k]=tmp;
                state.val = tmp_val;
            }
        }
        pq[prev]=priority_queue<State>();
    }
    auto best = pq[D&1].top().out;
    for (int i = 0; i < D; ++i) {
        printf("%d\n",best[i]+1);
    }

}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x3fffffffffffffff;
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; }
//template end

template<typename M,typename N=M>
struct LazySegmentTree{
    using F=function<M(M,M)>; using G=function<M(M,N)>; using H=function<N(N,N)>;
    int sz,height; vector<M> data; vector<N> lazy;
    const F f;const G g; const H h; const M m1; const N n1;
    LazySegmentTree(int n,const F f,const G g,const H h,const M &m1,const N n1):f(f),g(g),h(h),m1(m1),n1(n1){
        sz=1,height=0; while(sz<n)sz<<=1,height++;
        data.assign(2*sz,m1); lazy.assign(2*sz,n1);
    }
    inline void build(vector<M> v){
        rep(i,0,v.size())data[i+sz]=v[i];
        rrep(k,sz-1,0)data[k]=f(data[2*k],data[2*k+1]);
    }
    inline M ref(int k){return lazy[k]==n1?data[k]:g(data[k],lazy[k]);}
    inline void recalc(int k){while(k>>=1)data[k]=f(ref(2*k),ref(2*k+1));}
    inline void thrust(int k){rrep(i,height,0)eval(k>>i);}
    inline void eval(int k){
        if(lazy[k]!=n1){
            lazy[2*k]=h(lazy[2*k],lazy[k]); lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
            data[k]=ref(k); lazy[k]=n1;
        }
    }
    inline void update(int a,int b,N x){
        thrust(a+=sz); thrust(b+=sz-1);
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
            if(l&1)lazy[l]=h(lazy[l],x),++l;
            if(r&1)--r,lazy[r]=h(lazy[r],x);
        }
        recalc(a); recalc(b);
    }
    inline M query(int a,int b){
        thrust(a+=sz); thrust(b+=sz-1);
        M L=m1,R=m1;
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
            if(l&1)L=f(L,ref(l++)); if(r&1)R=f(ref(--r),R);
        } return f(L,R);
    }
};

vector<pair<int,int>> rng[200010];

int main(){
    int n,m; scanf("%d%d",&n,&m);
    rep(rot,0,m){
        int l,r,a; scanf("%d%d%d",&l,&r,&a);
        l--; r--;
        rng[r].push_back({l,a});
    }
    LazySegmentTree<ll> seg(n,
    [](ll a,ll b){return max(a,b);},
    [](ll a,ll b){return a+b;},
    [](ll a,ll b){return a+b;},0,0);
    rep(i,0,n){
        ll val=seg.query(0,i);
        seg.update(i,i+1,val);
        for(auto p:rng[i])seg.update(p.first,i+1,p.second);
    }
    printf("%lld\n",seg.query(0,n));
    return 0;
}


Measured memory_bytes: 19328
#include<bits/stdc++.h>
using namespace std;
int n, a[200010];
int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+1+n);
    for(int i=1; i<n; i++)
    {
        if(a[i] == a[i+1])
        {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
}


Measured memory_bytes: 1024
#include <iostream>
#include <queue>
#include <algorithm>

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

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

const int inf = 2e8;

int n, m, s;
int d[14348907];

V seq(){
	V v(n);
	rep(i, n){
		v[i] = i;
	}
	return v;
}

int pack(const VV& v){
	V p(n);
	rep(i, 3){
		for(int x: v[i]){
			p[x] = i;
		}
	}

	int k = 0;
	for(int i = n - 1; i >= 0; --i){
		k *= 3;
		k += p[i];
	}
	return k;
}
VV unpack(int k){
	VV v(3, V());
	rep(i, n){
		v[k % 3].push_back(i);
		k /= 3;
	}
	return v;
}

VV read(){
	VV v(3, V());
	rep(i, 3){
		int k;
		cin >> k;
		rep(j, k){
			int x;
			cin >> x;
			v[i].push_back(x - 1);
		}
	}
	return v;
}

VV swap_cup(VV v, int a, int b){
	if(!v[a].empty() || !v[b].empty()){
		if(!v[a].empty() && !v[b].empty()){
			if(v[a].back() > v[b].back()){
				swap(a, b);
			}	
		}
		else if(v[b].empty()){
			swap(a, b);
		}
		v[a].push_back(v[b].back());
		v[b].pop_back();
	}
	return v;
}

int main(){
	while(1){
		cin >> n >> m;
		if(!n){
			break;
		}
		s = pack(read());

		int f = pack({seq(), {}, {}});
		int g = pack({{}, {}, seq()});

		fill_n(d, sizeof(d) / sizeof(d[0]), inf);

		queue<int> q;
		d[s] = 0;
		q.push(s);
		while(!q.empty()){
			int v = q.front();
			q.pop();
			VV k = unpack(v);
			bool end = false;
			rep(i, 2){
				int t = pack(swap_cup(k, 1, i * 2));
				if(d[t] == inf){
					d[t] = d[v] + 1;
					q.push(t);
					if(t == f || t == g){
						end = true;
						break;
					}
				}
			}
			if(end){
				break;
			}
		}
		
		int ans = min(d[f], d[g]);
		cout << (ans <= m ? ans : -1) << endl;
	}
	return 0;
}

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

#define ll long long
#define pb push_back
#define N 1000000007
#define nmax 200001
#define pll pair<ll,ll>
#define fill_nums(A,n) for(ll i=0;i<n;i++) scanf("%lld",&A[i]);
#define fill_edges(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1); adj[b-1].pb(a-1);}
#define fill_direct(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1);}

ll extended_gcd(ll a, ll b, ll &x, ll &y) {
	if(a==0) {
		x = 0;
		y = 1;
		return b;
	}

	ll x1,y1;
	ll gcd = extended_gcd(b%a,a,x1,y1);

	x = y1 - (b/a)*x1;
	y = x1;

	return gcd;
}

ll solve(vector<vector<ll>> &dp, vector<vector<ll>> &adj, ll idx, ll mask) {

	ll n = adj.size();
	if(mask==0)
		return 1;

	if(dp[idx][mask]!=-1)
		return dp[idx][mask];

	ll res = 0;

	for(ll i=0;i<n;i++) {
		if((mask & (1<<i)) != 0 && adj[idx][i]) {
			res = (res + solve(dp,adj,idx-1,mask^(1<<i)))%N;
		}
	}

	dp[idx][mask] = (res+N)%N;
	return dp[idx][mask];
}

int main() {
    
   	ll n; cin>>n;
   	vector<pair<ll,ll>> vec(n);
   	for(int i=0;i<n;i++) {
   		scanf("%lld",&vec[i].first);
   	}

   	for(int i=0;i<n;i++) {
   		scanf("%lld",&vec[i].second);
   	}

   	map<ll,ll> vals;

   	ll maxi = 0;
   	for(int i=0;i<n;i++) {
   		
   		ll a = vec[i].first;
   		ll b = vec[i].second;

   		if(vals.empty()) {
   			vals[a] = b;
   			maxi = max(maxi, b);
   		}
   	
   		else {
   			map<ll,ll>::iterator it;
   			it = vals.lower_bound(a); 
   			ll c = 0;
   			if(it == vals.begin()) {
   				c = b;
   			}
   			else {
   				it--;
   			 	c = (*it).second + b;
   			}

   			
   			while(true) {
   				it = vals.lower_bound(a);
   				if(it == vals.end())
   					break;

   				if((*it).second<c || ((*it).second==c) && (*it).first>a)
   					vals.erase((*it).first);
   				else 
   					break; 
   			}
   			vals[a] = c;
   			maxi = max(maxi, c);
   		}
   	}

   	cout<<maxi<<endl;

	return 0;
}


 

Measured memory_bytes: 15872
int main(){
     
    int i=1, n,x;
 
    scanf("%d", &n);
    while (1){
        x = i;
        if (x % 3 == 0){
            printf(" %d", i);
        }
        else{
            while (1){
                if (x % 10 == 3){
                    printf(" %d", i);
                    break;
                }
                x /= 10;
                if (!x)break;
            }
             
        }
 
        if (++i > n) break;
    }
 
    printf("\n");
 
    return 0;
}

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

using ll = long long;

int main() {
  int n; cin >> n;
  vector<ll> la(n);
  for (int i = 0; i < n; ++i) {
    cin >> la[i];
  }
  sort(la.begin(), la.end());
  ll ans = la[n-1];
  int cnt = 1;
  for (int i = n-2; i > 0; --i) {
    // cout << i << " " << cnt << " " << la[i] << endl;
    ans += la[i];
    ++cnt;
    if (cnt > n-2) break;
    ++cnt;
    ans += la[i];
    if (cnt > n-2) break;
  }
  cout << ans << endl;
}



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

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var nm = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var n = nm[0];
        var m = nm[1];
        var ks = new int[n];
        var answers = new int[n][];
        for (int i = 0; i < ks.Length; i++)
        {
            var xs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            ks[i] = xs[0];
            answers[i] = xs.Skip(1).ToArray();
        }

        var set = new HashSet<int>(E.Range(1, m));
        for (int i = 0; i < answers.Length; i++)
        {
            set.IntersectWith(answers[i]);
        }
        Console.WriteLine(set.Count);
    }
}


Measured memory_bytes: 13536
m,d = map(int,input().split(" "))
count = 0
for i in range(1, m+1) :
  for j in range(1, d+1) :
    if j < 10 :
      continue
    str_j = str(j)
    d1, d2 = int(str_j[0]), int(str_j[1])
    if d1 < 2 or d2 < 2 :
    	continue
    temp = d1 * d2
    if temp == i :
      count+=1
print(count)

Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
using namespace std;

int main(void){
  int hour, min, sec;
  cin >> sec;
  hour = sec/3600;
  sec  = sec - hour*3600;
  min  = sec/60;
  sec  = sec - min*60;
  printf("%d:%d:%d\n", hour, min, sec);
  return 0;
}



Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
//////////////////////////////////

int main() {
    int n; cin >> n;
    vector<int> b(n-1);
    for(int i=0; i<n-1; i++) cin >> b[i];
    vector<int> a(n, 0);
    a[0] = b[0];
    a[n-1] = b[n-2];
    for(int i=1; i<n-1; i++) {
        a[i] = min(b[i-1], b[i]);
    }
    long long ans = 0;
    for(int i=0; i<n; i++){
        ans += a[i];
    }
    cout << ans << endl;

    return 0;
}

// EOF


Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[MAX][MAX];

void dijkstra(){
  int i, v, minv;
  int d[MAX], color[MAX];

  for(i = 0; i < n; i++){
    d[i] = INFTY;
    color[i] = WHITE;
  }

  d[0] = 0;
  color[0] = GRAY;
  while(1){
    minv = INFTY;
    int u = -1;
    for(i = 0; i < n; i++){
      if(minv > d[i] && color[i] != BLACK){
	u = i;
	minv = d[i];
      }
    }
    if(u == -1) break;
    color[u] = BLACK;
    for(v = 0; v < n; v++){
      if(color[v] != BLACK && M[u][v] !=INFTY){
	if(d[v] > d[u] + M[u][v]){
	  d[v] = d[u] + M[u][v];
	  color[v] = GRAY;
	}
      }
    }
  }
  for(i = 0; i < n; i++){
    printf("%d ",i);
    if(d[i] != INFTY) printf("%d\n",d[i]);
    else printf("-1\n");
  }
}

int main(){
  int i, j;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      M[i][j] = INFTY;
    }
  }

  int k, c, u, v;
  for(i = 0; i < n; i++){
    scanf("%d%d",&u,&k);
    for(j = 0; j < k; j++){
      scanf("%d%d",&v,&c);
      M[u][v] = c;
    }
  }

  dijkstra();

  return 0;
}

Measured memory_bytes: 636
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int WHITE = 0, GREY = 1, BLACK = 2;

struct CC {
    int n;
    vector<vector<int>> g;
    vector<int> color;
    vector<int> component;
    int cId = 0; //component id
    
    CC (int n) : n(n) {
        g.assign(n, vector<int>(0));
        color.assign(n, WHITE);
        component.assign(n, -1);
    }
    
    void addEdge (int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    void solve () {
        for (int i = 0; i < n; i++) {
            if (color[i] == WHITE) {
                cId++;
                bfs(i);
            }
        }
    }
    
    void bfs (int s) {
        queue<int> q;
        q.push(s);
        color[s] = GREY;
        component[s] = cId;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : g[u]) {
                if (color[v] == WHITE) {
                    q.push(v);
                    color[v] = GREY;
                    component[v] = cId;
                }
            }
        }
    }
};

int main() {
    
    int n, m;
    cin >> n >> m;
    CC cc(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        cc.addEdge(u, v);
    }
    
    cc.solve();
    
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        if (cc.component[u] == cc.component[v]) {
            cout << "yes" << endl;
        }
        else {
            cout << "no" << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  int b;
  cin >> a >> b;
  vector<int> s(b);
  for (int i=0;i < b;i++){
    cin >> s.at(i);
  }
  int h = a + s.at(0) - s.at (b-1);
  for (int i=0;i < b-1;i++){
  h = max(s.at(i+1) - s.at(i),h);
  }
    cout << a-h << endl;
}

Measured memory_bytes: 1024
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 100000000
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define mp make_pair
ll mod = 10e9+7;
ll mod2 = 998244353;

int main(){
	int a,b;cin>>a>>b;
	cout<<(a*3+b)/2<<endl;;
}

Measured memory_bytes: 3528
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto X = new int[](N+1);
    int[][int] Y;
    X[0] = 0;
    Y[0] = [0];
    foreach (i; 0..N) {
        int c = S[i] - 'a';
        X[i+1] = X[i] ^ (1 << c);
        Y[X[i+1]] ~= i+1;
    }


    auto dp = new int[](N+1);
    dp.fill(1 << 29);
    dp[0] = 0;
    int[int] used;

    foreach (i; 0..N) {
        foreach (j; 0..26) {
            int next = X[i] ^ (1 << j);
            if (next in Y && (!(next in used) || used[next] > dp[i])) {
                used[next] = dp[i];
                foreach (m; Y[next]) {
                    dp[m] = min(dp[m], dp[i]+1);
                }
            }
        }

        if (X[i] in Y && (!(X[i] in used) || used[X[i]] > dp[i])) {
            used[X[i]] = dp[i];
            foreach (m; Y[X[i]]) {
                dp[m] = min(dp[m], dp[i]+1);
            }
        }
    }

    dp[N].writeln;
}


Measured memory_bytes: 39224
#include <iostream>

using namespace std;

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

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

    int ans = n / 2;
    if (n % 2 == 1)
    {
        cout << ans + 1 << endl;
    }
    else
    {
        cout << ans << endl;
    }
    
}

Measured memory_bytes: 256
h,w=map(int,input().split())
L=[list(input()) for i in range(h)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
flag=0
for i in range(h):
    for j in range(w):
        c=0
        d=0
        if L[i][j]=='#':
            for k in range(4):
                if (j+dx[k] in range(w)) and (i+dy[k] in range(h)):
                    d+=1
                    if L[i+dy[k]][j+dx[k]]=='.':
                        c+=1
            if c!=0 and c==d:
                flag=1
print('Yes' if flag==0 else 'No')


Measured memory_bytes: 3064
while gets
n=$_.to_i
d=(0...n).to_a
r=gets.split.map(&:to_i)
r.each{|e|
a=d[n/2..-1]
b=d[0...n/2]
a2=[];a.each_slice(e){|f|a2<<f}
b2=[];b.each_slice(e){|f|b2<<f}
d=a2.zip(b2).flatten[0...n]
}
p d[n-1]
end

Measured memory_bytes: 5948
/* Coached by rainboy */
#include <stdio.h>
#include <stdlib.h>

#define N 100000
#define M 100000

int aa[N], bb[M], cc[M];

int compare_a(const void *a, const void *b) {
	int ia = *(int *) a;
	int ib = *(int *) b;

	return ia - ib;
}

int compare_i(const void *a, const void *b) {
	int i = *(int *) a;
	int j = *(int *) b;

	return cc[j] - cc[i];
}

int main() {
	static int ii[M];
	int n, m, i, j, k;
	long long ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < m; i++) {
		scanf("%d%d", &bb[i], &cc[i]);
		ii[i] = i;
	}
	qsort(aa, n, sizeof *aa, compare_a);
	qsort(ii, m, sizeof *ii, compare_i);
	for (i = j = 0; j < m; i = k, j++)
		for (k = i; k < n && bb[ii[j]] > 0; k++)
			if (cc[ii[j]] > aa[k]) {
				aa[k] = cc[ii[j]];
				bb[ii[j]]--;
			}
	ans = 0;
	for (i = 0; i < n; i++)
		ans += aa[i];
	printf("%lld\n", ans);
	return 0;
}


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

using lli = long long;
#define X first
#define Y second

int main() {
  int n;
  cin >> n;
  
  vector<pair<lli, lli>> v(n);
  for (auto &x : v) {
    cin >> x.X >> x.Y;
    x.X -= x.Y;
    x.Y += x.Y;
    x.Y += x.X;
  }
  
  sort(v.begin(), v.end(), [](auto a, auto b) {
    if (a.Y == b.Y) return a.X < b.X;
    return a.Y < b.Y;
  });
  
  lli ri = -1E18, bk = 0;
  for (auto x : v) {
    if (x.X < ri) ++bk;
    else ri = x.Y;
  }
  
  cout << n - bk << "\n";
  
  return 0;
}


Measured memory_bytes: 1792
import sys
import math


#0:中央 1:南 2:東 3:西 4:北 5:裏側
class Dice():

    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
        self.order = 'NNNNWNNNWNNNENNNENNNWNNN'

    def setNumber(self,n0,n1,n2,n3,n4,n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5


    def roll(self,loc):
        for i in range(6):
            self.work[i] = self.number[i]

        if loc == 'E':
            self.setNumber(self.work[3],self.work[1],self.work[0],self.work[5],self.work[4],self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1],self.work[5],self.work[2],self.work[3],self.work[0],self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4],self.work[0],self.work[2],self.work[3],self.work[5],self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2],self.work[1],self.work[5],self.work[0],self.work[4],self.work[3])


    def query(self,top_num,front_num):

        self.save_data = [i for i in range(6)]
        #元の値の保存
        for i in range(len(self.number)):
            self.save_data[i] = self.number[i]

        ret = -1

        for i in range(len(self.order)):
            self.roll(self.order[i])
            if self.number[0] == top_num and self.number[1] == front_num:
                ret = self.number[2]
                break

        #元の値の復元
        for i in range(len(self.number)):
            self.number[i] = self.save_data[i]

        return ret

dice = Dice()
table = list(map(int,input().split()))
dice.setNumber(table[0], table[1], table[2], table[3], table[4], table[5])

num_query = int(input())
for loop in range(num_query):
    top_num,front_num = map(int,input().split())
    print("%d"%(dice.query(top_num, front_num)))


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

/* {{{ */
#define PI(N) ((M_PI * (N)) / 180) //?§???????????????¢??????????????????
#define CL(N) (cout << (N) << endl)
#define DCT(N) (cout << "debug " << (N) << endl)
#define REP(i, N) for (int i = 0; i < (N); i++)
/* }}} */

int main()
{
    int d, a, sum_angle = 90;
    double x, y;

    x = y = 0.0;

    while (scanf("%d,%d", &d, &a), d || a){
        x += d * cos(PI(sum_angle));
        y += d * sin(PI(sum_angle));

        sum_angle = (sum_angle - a + 360) % 360;
    }

    CL((int)x);
    CL((int)y);

    return (0);
}

Measured memory_bytes: 3408
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4,avx2,abm,fma")
#include <bits/stdc++.h>
using namespace std;
#define _USE_MATH_DEFINES

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;

const char nl = '\n';
const ll INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const ld EPS = 1e-13;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());



int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(10);

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

	ll ans = INFLL;
	for(int x=1; x<=100; x++) {
		ll sum = 0;
		for(int j=0; j<n; j++) {
			sum += (ll)(a[j]-x)*(a[j]-x);
		}
		ans = min(ans, sum);
	}
	cout << ans << nl;

	return 0;
}


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

long long int M = 1e+9 + 7;
long long int power(long long int x, long long int n)
{
    if (n == 0)
        return (long long)1;
    else if (n % 2 == 0) //n is even
        return power((x * x) % M, n / 2);
    else //n is odd
        return (x * power((x * x) % M, (n - 1) / 2)) % M;
}
long long int cans(long long int p, long long int q)
{
    return ((p * power(q, M - 2)) % M + M) % M;
}
const int N = 4e+5 + 5;
long long int n, fact[N], facti[N];

long long int ncr1(int i, int j)
{
    long long int ans = (fact[i] * facti[j]) % M;
    ans = (ans * facti[i - j]) % M;
    return ans;
}
int main()
{
    long long int k;
    cin >> n >> k;
    // cout<<a<<" "<<b<<" ";
    fact[0] = facti[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (i * fact[i - 1]) % M;
        facti[i] = cans(1, fact[i]);
    }
    long long int ans = 0;
    for (int i = 0; i <= min(k,n-1); i++)
        ans = (ans + (ncr1(n, i) * ncr1(n - 1, n - i - 1)) % M) % M;
    cout << ans;
}

Measured memory_bytes: 6528
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int mypow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a;
		a *= a;
		n >>= 1;
	}
	return res;
}

int solve(int N) {

	vector<int> vec753;
	int bit_used = 0, range = 9, res = 0;
	int tmp, ternary, n753;

	for (int digit = 3; digit <= 9; digit++) {

		range *= 3;

		for (int i = 0; i <= range; i++) {

			bit_used = 0;
			ternary = i;
			n753 = 0;

			for (int j = 0; j < digit; j++) {

				tmp = ternary % 3;
				ternary /= 3;
				
				if (tmp == 0) {
					n753 += 3 * mypow(10,j);
					bit_used |= 1;
				}				
				if (tmp == 1) {
					n753 += 5 * mypow(10, j);
					bit_used |= 2;
				}
				if (tmp == 2) {
					n753 += 7 * mypow(10, j);
					bit_used |= 4;
				}

			}

			if (n753 > N) break;
			if (!(bit_used ^ 7)) {
				vec753.push_back(n753);
				res++;
			}

		}

	}

	return res;

}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	cout << solve(N) << "\n";

	return 0;

}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define REP(i,a) for(int i = 0; i < (a);i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using Graph = vector < vector<int>>;
long int sum[200020] = {};
int main() {
	int N;
	cin >> N;
	vector<pair<string,pair<int,int>>> list;
	for (int i = 1; i <= N; i++) {
		string s;
		pair<int, int> k;
		pair<string, pair<int, int>> g;
		int a;
		int b;
		cin >> s >> a;
		a = -a;
		k.first = a;
		k.second = i;
		g.first = s;
		g.second = k;
		list.push_back(g);
	}
	sort(list.begin(), list.end());
	for (int i = 0; i < N; i++) {
		cout << get<1>(get<1>(list[i])) << endl;
	}
}

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

int main() {
	int n;
	cin>>n;
	int arr[n];
	int brr[n];
	for(int i=0;i<n;i++){
	    cin>>arr[i];
	    brr[i]=arr[i];
	}
	sort(arr,arr+n);
	int max=arr[n-1];
	for(int i=0;i<n;i++){
	    if(brr[i]==max){
	        cout<<arr[n-2]<<"\n";
	    }
	    else cout<<max<<"\n";
	}
	return 0;
}


Measured memory_bytes: 3200
import sys
import bisect
from itertools import product
def input(): return sys.stdin.readline().strip()
A,B,Q = map(int,input().split())
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
stlist = [s,t]
ab = [A,B]
for i in range(Q):
    x = int(input())
    cand = []
    for i in range(2):
        st = stlist[i]
        cand1 = set()
        l1 = bisect.bisect_left(st,x)
        if 0 <= l1 <= ab[i]-1:
            cand1.add(st[l1])
        if 0 <= l1-1 <= ab[i]-1:
            cand1.add(st[l1-1])
        cand.append(cand1)
    ans = float('inf')
    for a,b in product(cand[0],cand[1]):
        c = min(abs(x-a)+abs(b-a),abs(x-b)+abs(b-a))
        ans = min(ans,c)
    print(ans)
        
        
    

Measured memory_bytes: 76764
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e3 + 3;


signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int a[N][N];
    int now[N];
    bool vis[N];
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        now[i] = 1;
        for (int j = 1; j < n; j++) {
            cin >> a[i][j];
        }
    }

    int ans = 0, op;
    bool ched = true;
    while(ched) {
        ans++;
        for (int i = 1; i <= n; i++) vis[i] = (now[i] == n);
        ched = false;
        for (int i = 1; i <= n; i++) {
            if(!vis[i]){
                op = a[i][now[i]];
                if (!vis[op]&&a[op][now[op]]==i){
                    ched = true;
                    // cerr << "DAY: " << ans << endl;
                    // cerr << "i: " <<i << " op: " << a[i][now[i]] << endl;
                    vis[i] = true, vis[op] = true;
                    now[op]++, now[i]++;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(now[i] != n) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans - 1 << endl;
    return 0;
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	int cnt = 0;
	for(char c : s)
		if(c == 'p')
			cnt++;
	cout << (int)s.size() / 2 - cnt << endl;
	return 0;
}


Measured memory_bytes: 512
#include<stdio.h>


 
int main() {

	int i,cnt=0,a, b,c;

	scanf("%d%d%d", &a, &b,&c);

	for (i = 100; i > 0; i--) {
		if (a%i == 0 && b%i == 0) cnt++;
		if (cnt == c)break;
		

	}
	printf("%d", i);


	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n;
  scanf("%d", &n);

  vector<int> v(n);
  REP(i,n){
    scanf("%d", &v[i]);
  }

  int ans = 0;
  int last = -1, sum = 0;
  REP(i,n){
    if(v[i] == last){
      sum++;
      if(i == n - 1){
        ans += sum / 2;
      }
    }else{
      ans += sum / 2;
      sum = 1;
      last = v[i];
    }
  }

  printf("%d\n", ans);
  return 0;
}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N,M = map(int,input().split())
ans=[0]*N
a = [list(map(int, input().split())) for _ in range(N-1)]

for _ in range(M):
    e,f = list(map(int, input().split()))
    ans[e-1] += f

trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])
    

def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)


Measured memory_bytes: 265244
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define N 1005
using namespace std;
typedef long long ll;
int a[305][305];
struct node
{
    int x;
    int y;
}p[90005];
int ans[90005];
int main()
{
    int h,w,d,len;
    scanf("%d%d%d",&h,&w,&d);
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++){
          scanf("%d",&a[i][j]);
          int n=a[i][j];
           p[n].x=i;
           p[n].y=j;
        }
    int q;
    len=h*w;
    scanf("%d",&q);
    for(int i=1;i<=d;i++)
    {
        int l=i,r=len,sum=0;
        ans[i]=0;
        while(l<=r-d)
        {
            sum=sum+abs(p[l].x-p[l+d].x)+abs(p[l].y-p[l+d].y);
            l=l+d;
            ans[l]=sum;
        }
 
    }
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",ans[r]-ans[l]);
    }
}


Measured memory_bytes: 2560
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>
#include <set>
#include <map>
#include <type_traits>
#include <cstdint>

typedef long long ll;

using namespace std;

//素因数分解
void factoring(ll n, map<ll, ll>& mp) {
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			mp[i]++;
			n /= i;
		}
	}
	if (n != 1) mp[n]++;
}

//絶対値
template<class T, class U = std::make_unsigned_t<T>>
U SafeAbs( T x ) {
    return x < 0 ? -static_cast<uintmax_t>(x) : x;
}

//最大・最小
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;
}

//xのn乗
ll mod_pow(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
//xの逆元
ll mod_inv(ll x, ll mod) {//O(log(mod))
    return mod_pow(x, mod - 2, mod);
}

//nCr
ll ncr(ll n, ll r, ll mod){
	ll res=1;
	ll num=1,den=1;
	for(ll i=n;i>=n-r+1;i--){
		(den*=i)%=mod;
	}
	for(ll i=1;i<=r;i++){
		(num*=i)%=mod;
	}
	
	res=den*mod_inv(num,mod);

	return res%mod;
}


//二分探索
bool isOk(ll index, ll key,vector<ll> &a, bool g){
	if(g){
		if(a[index]<key){
			return true;
		}
	}
	else{
		if(a[index]>key){
			return true;
		}
	}
	return false;
}

ll bin_search(ll key, vector<ll> &a, bool g){
	
	ll l=-1;
	ll r=a.size();

	if(g){
		l=a.size();
		r=-1;
	}

	while(abs(r-l)>1){
		ll mid = (l+r)/2;
		if(isOk(mid, key, a, g)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	return r;
}

//最大公約数
ll gcd(ll m, ll n) {
    if (n == 0)return m;
    return gcd(n, m % n);
}
//最小公倍数
ll lcm(ll m, ll n) {
    return m / gcd(m, n) * n;
}

int main(){

	ll n;
	cin>>n;

	ll ans=0;

	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++){
			for(ll k=1;k<=n;k++){
				ans+=gcd(i,gcd(j,k));
			}
		}
	}

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


Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb emplace_back
const double pi = acos(-1);
const double EPS = 1e-10;

vi solve(int i,int j,vii ans){
  vi res(i);
  if (j == 0) {
    REP(k,i) res[k] = k+1;
    return res;
  } else {
    for (int k = 0; k < i; k++) {
      if(k < j){
        res[k] = ans[k][j-1];
      }else if(k == j){
        res[k] = ans[j-1].back() + 1;
      }else{
        res[k] = res[k-1] + 1;
      }
    }
    return res;
  }
}

int main(){
  int n;
  cin >> n;
  bool flag = false;
  int i = 1;
  for (; i*(i+1)/2 <= n; i++) {
    if (i*(i+1)/2 == n) {
      flag =true;
      break;
    }
  }
  if (flag) {
    cout << "Yes" << endl;
    cout << i+1 << endl;
    vii ans;
    REP(j,i+1){
      cout << i;
      ans.pb(solve(i,j,ans));
      REP(k,i){
        cout << " " << ans[j][k];
      }
      cout << endl;
    }
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3072
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

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

	if (h % a != 0)
		cout << h / a + 1 << endl;
	else cout << h / a << endl;
	
	return 0;
}

Measured memory_bytes: 3580
import java.util.*;

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

        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            int digitSum = 0;
            int tmp = i;
            while (tmp > 0) {
                digitSum += tmp % 10;
                tmp /= 10;
            }
            if (a <= digitSum && digitSum <= b)
                sum += i;
        }

        System.out.println(sum);
    }
}

Measured memory_bytes: 23636
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('a1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    N, R = read_int_list()
    if N >= 10:
      R == N 
    else:
      R = 100 * (10 - N) + R
    print(R)


main()


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

int n, p, o, a;
long ans = 1;

main()
{
    cin >> n >> p;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        o += (a % 2);
    }
    for (int i = 0; i < n; i++)
        ans *= 2;
    if (o == 0)
    {
        cout << (p == 1 ? 0 : ans) << endl;
    }
    else
        cout << ans / 2 << endl;
}

Measured memory_bytes: 256
import sys

def solve():
    N = int(input())
    word = dict()
    for i in range(N):
        s = input()
        if s in word: word[s] += 1
        else: word[s] = 1

    L = []
    for key in word:
        L.append((word[key], key))
    L.sort(reverse = True)
    maxs = L[0][0]
    Ans = []
    for num, s in L:
        if num == maxs: Ans.append(s)
    Ans.sort()
    for a in Ans:
        print(a)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 45400