akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define Pair pair<int,int>
#define lPair pair<ll,ll>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define debug(a) cout << a << endl;
const ll INF = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
ll N,M;//V == N,E == M;
ll a,b,c;
struct edge{ll from,to,cost;};
vector<edge> es;
ll d[1000];
//頂点sからの最大距離
bool BellmanFord(){
    for(int i = 0; i < N; i++) d[i] = -INF;
    d[0] = 0;
    for(int i = 0; i < N-1; i++){ //**
        for(int j = 0; j < M; j++){
            edge e = es[j];
            if(d[e.from] != -INF && d[e.to] < d[e.from]+e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    ll dv = d[N-1];
    for(int i = 0; i < N; i++){ //**
        for(int j = 0; j < M; j++){
            edge e = es[j];
            if(d[e.to] != -INF && d[e.to] < d[e.from]+e.cost){
                d[e.to] = d[e.from]+e.cost;
            }
        }
    }
    if(d[N-1] > dv) return 0;
    else return 1;

}

int main(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        es.push_back({a,b,c});
    }
    if(BellmanFord()) cout << d[N-1] << endl;
    else cout << "inf" << endl;
    return 0;
}

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> x(n);
	for (int i = 0; i < n; i++)
		cin >> x[i];
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans += min(abs(x[i]), abs(k - x[i]));
	ans *= 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <cstring>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
typedef long long ll;
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

template<typename T> //最大公約数
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T> //最小公倍数
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}


struct UnionFind {
	vector<int> par, rank, cnt;
	UnionFind(int n) : par(n), rank(n, 0), cnt(n, 1){
		for(int i = 0; i < n; ++i) par[i] = i;
	}
 
	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}
 
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
 
		if (rank[x] < rank[y]) swap(x, y);
 
		par[y] = x;
		cnt[x] += cnt[y];
		if (rank[x] == rank[y]) rank[x]++;
	}
 
	bool same(int x, int y) {
		return find(x) == find(y);
	}
 
	int size(int x) {
		return cnt[find(x)];
	}
};



int main(){
    int N, Q; cin >> N >> Q;
    UnionFind uf(N);
    for (int i = 0; i < Q; i++){
        int com, x, y; cin >> com >> x >> y;
        if (com == 0){
            uf.unite(x, y);
        } else {
            cout << uf.same(x, y) << endl;
        }
    }
}


Measured memory_bytes: 3224
from collections import Counter
N = int(input())
val2ind = Counter(list(map(int, input().split())))
ans = sum([key*val2ind[key] for key in val2ind])
Q = int(input())

for _ in range(Q):
    B, C = list(map(int, input().split()))
    if B in val2ind:
        cand = val2ind[B]
        del val2ind[B]
        if C not in val2ind:
            val2ind[C] = cand
        else:
            val2ind[C] += cand
        ans = ans+(C-B)*cand
    print(ans)

Measured memory_bytes: 88728
#include <bits/stdc++.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
//int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
//int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
const ll MOD = 1000000007;
//const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

signed main() {
    fio();
    string s;
    cin >> s;
    rep (i, s.size()) {
        if (s[i] == '7') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

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

int main() {
	ll A, B, N;
	ll maxval = numeric_limits<ll>::min(), val;
	cin >> A >> B >> N;

	if (B <= N) {
		val = (A * (B - 1)) / B;
	}
	else {
		val = ((A * N) / B) - (A * (N / B));
	}
	cout << val << endl;
	/*
	for (ll x = B - 1; x <= N; x += B) {
		val = ((A * x) / B) - (A * (x / B));
		maxval = max(maxval, val);
	}

	val = ((A * N) / B) - (A * (N / B));
	maxval = max(maxval, val);

	cout << maxval << endl;
	*/
	return 0;
}

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

int64_t f(int64_t n){
    return n*(n-1)/2;
}

int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin>>n;
    
    vector<int64_t> a(n);
    rep(i,n)cin>>a[i], a[i]--;
    
    vector<int64_t> m(n,0);
    rep(i,n)m[a[i]]++;
    
    int64_t ans = 0;
    rep(i,n)ans += f(m[i]);
    
    rep(i,n){
        //cout << ans -f(m[a[i]]) + f(m[a[i]]-1) << endl;
        printf("%lld\n", ans -f(m[a[i]]) + f(m[a[i]]-1));
    }
    
    return 0;
}

Measured memory_bytes: 5760
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

signed main(){
    
    int n; cin >> n;
    set<string> st;
    vector<string> mon(n);
    for(int i = 0; i < n; i++){
        cin >> mon[i];
        st.insert(mon[i]);
    }
    int m; cin >> m;
    vector<string> kukui(m);
    for(int i = 0; i < m; i++){
        cin >> kukui[i];
        st.insert(kukui[i]);
    }
    
    int ans = 0;
    for(auto e : st){
        int tmp = 0;
        for(auto f : mon){
            tmp += (e == f);
        }
        for(auto f : kukui){
            tmp -= (e == f);
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main { 
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		while(true) {
			int n = stdIn.nextInt();
			int m = stdIn.nextInt();
			if(n == 0 && m == 0) break;
			int[] hS = new int[n+1];
			int[] wS = new int[m+1];
			int hmax = 0;
			int wmax = 0;
			for(int i = 1; i < n+1; i++) {
				hS[i] = hS[i-1] + stdIn.nextInt();
				if(hS[i] > hmax) {
					hmax = hS[i];
				}
			}
			for(int i = 1; i < m+1; i++) {
				wS[i] = wS[i-1] + stdIn.nextInt();
				if(wS[i] > wmax) {
					wmax = wS[i];
				}
			}
			int count = 0;
			int[] listhS = new int[hmax+1];
			int[] listwS = new int[wmax+1];
			int max = Math.min(hmax, wmax);
			for(int i = 0; i < n+1; i++) {
				for(int j = i + 1; j < n+1; j++) {
					listhS[hS[j] - hS[i]]++;
				}
			}
			for(int k = 0; k < m+1; k++) {
				for(int l = k + 1; l < m+1; l++) {
					listwS[wS[l] - wS[k]]++;
				}
			}
			for(int i = 0; i < max+1; i++) {
				count += listhS[i] * listwS[i];
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 63024
#coding: utf-8
N = int(input())
l = []
for i in range(N):
    a = list(map(int, input().split()))
    if a[2] > 0:
      l.append(a)
if len(l) >= 2:
    for i in range(len(l)-1):
        ans = []
        for cx in range(101):
            for cy in range(101):
                if l[i][2] + abs(l[i][0] - cx) + abs(l[i][1] - cy) == l[i+1][2] + abs(l[i+1][0] - cx) + abs(l[i+1][1] - cy) and l[i][2] != 0 and l[i+1][2] != 0:
                    if i == 0:
                        ans.append([cx, cy])
                    else:
                        if [cx, cy] in ansn:
                            ans.append([cx, cy])
        ansn = ans[:]
        if len(ans) == 1:
            break
    print(ans[0][0], ans[0][1], l[0][2] + abs(l[0][0] - ans[0][0]) + abs(l[0][1] - ans[0][1]))
else:
    print(l[0][0], l[0][1], l[0][2])

Measured memory_bytes: 3956
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

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; }

using ll = long long;

const ll mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  std::vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

ll N;
ll C[200010];
mint two[200010];
combination comb( 200010 );

int main()
{
  std::cin >> N;

  rep( i, N )
    std::cin >> C[i];

  std::sort( C, C+N );
  std::reverse( C, C+N );

  two[0] = 1;
  rep( i, N+1 )
    two[i+1] = two[i]*2;

  mint ans = 0;

  rep( i, N )
    ans += (two[N-2]*i+two[N-1])*C[i];

  ans *= two[N];

  std::cout << ans.x << std::endl;

  return 0;
}

Measured memory_bytes: 6528
#include<iostream>
int main(){
  int n,k,q;
  std::cin >> n>> k >> q;
  int a[n] = {};
  int i;
  int p;
  for (i=0;i<q;i++){
    std::cin >> p;
    a[p-1] += 1;
  }
  for(i=0;i<n;i++){
    if(a[i] > q-k) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
  }
}

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

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

	vector<int> p(n);
	for (int i = 0; i < n; i++)
	{
		cin >> p.at(i);
	}

	int max = *max_element(p.begin(), p.end());
	int sum = accumulate(p.begin(), p.end(), 0);

	cout << sum - max + max / 2 << endl;
}


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

const int B=999999937;
const int P=1000000007;

vector<long long> gen_hash(const string &s){
	vector<long long> hash(s.size());
	long long c=0;
	for(int i=0;i<s.size();i++){
		c=(c*B+s[i])%P;
		hash[i]=c;
	}
	return hash;
}
long long pow_binary_mod(long long x,long long y,long long mod){
	long long z=1;
	for(;y;y>>=1){
		if((y&1)!=0)z=z*x%mod;
		x=x*x%mod;
	}
	return z;
}

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

	string s;
	cin>>s;
	int ls=s.size();
	vector<long long> v=gen_hash(s);

	//int T;
	//for(cin>>T;T--;){
		string q;
		cin>>q;
		int lq=q.size();
		long long hash=gen_hash(q)[lq-1];
		long long Brev=pow_binary_mod(B,lq,P);
		vector<int> r;
		int i=lq-1;
		for(;i<ls;i++){
			if(v[i]==((i==lq-1?0:v[i-lq])*Brev+hash)%P){
				r.push_back(i-lq+1);
			}
		}
		if(!r.empty()){
			for(int i=0;i<r.size();i++)printf("%d\n",r[i]);
			//puts("1");
		}else{
			//puts("0");
		}
	//}
}

Measured memory_bytes: 16180
num = int(input())
line = list(map(int, input().split()))
count = 0
for i in range(1,num):
    for j in range(i):
        if line[i-j] < line[i-j-1]:
            a = line[i-j]
            line[i-j] = line[i-j-1]
            line[i-j-1] = a
            count+= 1
        else:
            break
line_str = [str(k) for k in line]
print(' '.join(line_str))
print(count)


Measured memory_bytes: 5604
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll Mod=1000000007;
ll i,j,k,n,m;
ll a[110];
ll dp[110][10];
int main(){
    a[0]=1;
    a[1]=1;
    a[2]=2;
    a[3]=3;
    for(i=4;i<=101;i++)(a[i]=a[i-1]+a[i-2])%=Mod;
    cin>>m>>n>>k;
    dp[0][1]=1;
    for(i=1;i<=m;i++){
        dp[i][1]=dp[i-1][1]*a[n-2+1]%Mod+dp[i-1][2]*a[n-3+1]%Mod;
        dp[i][1]%=Mod;
        dp[i][n]=dp[i-1][n]*a[n-2+1]%Mod+dp[i-1][n-1]*a[n-3+1]%Mod;
        dp[i][n]%=Mod;
        for(j=2;j<n;j++){
            dp[i][j]=(dp[i-1][j-1]*a[j-3+1]%Mod*a[n-j-1+1]%Mod+dp[i-1][j+1]*a[j-2+1]%Mod*a[n-j-2+1]%Mod)%Mod+dp[i-1][j]*a[j-2+1]%Mod*a[n-j-1+1];
            dp[i][j]%=Mod;
        }
    }
    cout<<dp[m][k]<<endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#define p 1000000007
using namespace std;
int n,m,dc[1010101],dr[1010101],r,c,pot;
long long ans=1;
void print()
{
	puts("0");
	exit(0);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		if(dr[x]) print();
		dr[x]=1;
	}
	for(int i=1,x;i<=m;i++)
	{
		scanf("%d",&x);
		if(dc[x]) print();
		dc[x]=1;
	}
	for(int i=n*m;i;i--)
	{
		if(dc[i]&&dr[i])
		{
			pot+=c+r;
			c++;r++;
		}
		else if(dc[i])
		{
			if(!r) print();
			(ans*=r)%=p;
			pot+=r-1;
			c++;
		}
		else if(dr[i])
		{
			if(!c) print();
			(ans*=c)%=p;
			pot+=c-1;
			r++;
		}
		else
		{
			if(!pot) print();
			(ans*=pot)%=p;
			pot--;
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 2304
#include <stdio.h>
#include <string.h>

int main(){
    char ar[1000]={};
    char temp[1000]={};
    int m,h,i,j;
    
    while(1){
        scanf("%s%d",ar,&m);
        if(strcmp(ar,"-")==0) break;
        
        for(i=0;i<m;i++){
        scanf("%d",&h);
        strncpy(temp,ar,h);
        strcpy(ar,ar+h);
        strcat(ar,temp);
        
        for(j=0;j<1000;j++) temp[j]=0;
        }
        printf("%s\n",ar);
    }
    
    return 0;
}


Measured memory_bytes: 2044
#include "bits/stdc++.h"
using namespace std;
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cout << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(V) (V).begin(), (V).end() 
#define x first
#define y second

using namespace std;

typedef long long ll;
template <typename T> using V = vector <T>;

int main() {fio;
	int N, W;
	cin >> N >> W;
	V <int> w(N), v(N);
	for(int i = 0; i < N; i++) {
		cin >> w[i] >> v[i];
	}
	V <ll> DP(W + 1, 0);
	for(int i = 0; i < N; i++) {
		V <ll> DPL = DP;
		for(int wc = w[i]; wc <= W; wc++) {
			DP[wc] = max(DPL[wc - w[i]] + v[i], DP[wc]);
		}
	}
	cout << *max_element(DP.begin(), DP.end());
	
    return 0;
}

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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    int a;
    cin>> a;

    cout<< a* (1+ a*( 1+ a));
    nl;


    return 0;
}




Measured memory_bytes: 3624
from heapq import *
from collections import defaultdict
from copy import deepcopy
from math import log
from itertools import accumulate

N=int(input())
A=list(map(int,input().split()))
X=[sum(A[:N])]
Xheap=A[:N]
heapify(Xheap)
for i in range(N,2*N):
    x=heappushpop(Xheap,A[i])
    S=X[-1]+A[i]-x
    X.append(S)
A.reverse()
Y=[sum(A[:N])]
Yheap=[-i for i in A[:N]]
heapify(Yheap)
for i in range(N,2*N):
    y=-heappushpop(Yheap,-A[i])
    S=Y[-1]+A[i]-y
    Y.append(S)
Y.reverse()
ans=-10**19
for i in range(N+1):
    ans=max(ans,X[i]-Y[i])
print(ans)


Measured memory_bytes: 120048
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 102;
const int M = 2505;
int n, m, k;
char s[N][N];
int a[N][2];
vector<int> g[M];
bool dp[N][N];
bool used[M];
int mt[N];
pii ord[M];
int sz;

bool dfs(int x) {
	if (used[x]) return false;
	used[x] = 1;
	for (int y : g[x]) {
		if (mt[y] == -1) {
			mt[y] = x;
			return true;
		}
	}
	for (int y : g[x]) {
		if (dfs(mt[y])) {
			mt[y] = x;
			return true;
		}
	}
	return false;
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", s[i]);
		for (int j = 0; j < m; j++) {
			if (s[i][j] == 'o') {
				a[k][0] = i;
				a[k][1] = j;
				k++;
				s[i][j] = '.';
			}
		}
	}
	for (int it = 0; it < k; it++) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				dp[i][j] = 0;
		dp[a[it][0]][a[it][1]] = 1;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (i + 1 < n && s[i + 1][j] != '#')
					dp[i + 1][j] |= dp[i][j];
				if (j + 1 < m && s[i][j + 1] != '#')
					dp[i][j + 1] |= dp[i][j];
			}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (dp[i][j])
					g[i * m + j].push_back(it);
			}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			ord[sz++] = mp(i + j, i * m + j);
	sort(ord, ord + sz);
	reverse(ord, ord + sz);
	for (int i = 0; i < k; i++)
		mt[i] = -1;
	int ans = 0;
	for (int i = 0; i < sz; i++) {
		if (dfs(ord[i].second)) {
			ans += ord[i].first;
			for (int j = 0; j < sz; j++)
				used[j] = 0;
		}
	}
	for (int i = 0; i < k; i++)
		for (int j = 0; j < 2; j++)
			ans -= a[i][j];
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 3588
# -*- coding: utf-8 -*-
u = 100000

f = [False]*(u+1)
for i in range(2, u+1):
    if not f[i]:
        for j in range(i+i, u+1, i):
            f[j] = True

c = [0]*(u+2)
for i in range(3, u+1, 2):
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
for i in range(3, u+1):
    c[i] += c[i-1]

q = int(input())
for i in range(q):
    s, e = map(int, input().split())
    print(c[e] - c[s-1])

Measured memory_bytes: 7156
def main():
  from collections import Counter
  from collections import defaultdict
  from collections import deque
  from itertools import accumulate
  from itertools import combinations
  from itertools import permutations
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row[:]]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int H ,W;
	cin >> H >> W;
	int N;
	cin >> N;
	vector<int> A(N);
	vector<vector<int> > res(H);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		
	}
	for (int i = 0; i < H; i++) {
		res[i].resize(W);
	}
	int k = 0;
	int o = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (i % 2 == 0) {
				k = j;
			}
			else {
				k = W - j - 1;
			}
			
			if (A[o] > 0) {
				A[o]--;
			}
			else {
				o++;
				A[o]--;
			}
			res[i][k] = o;
			
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (j > 0) {
				cout << " ";
			}
			cout << (res[i][j] + 1);
		}
		cout << endl;
	}
	return 0;
	
}

Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <climits>
#include <string>
#include <vector>

using namespace std;

long long dp(long long don, int g_val, int g_w, int s_val, int s_w, int b_val, int b_w) {
    vector<long long> dpdp(don+1);
    for (int i=1; i<don+1; i++) {
        long long buf_g = 0, buf_s = 0, buf_b = 0;
        if (i >= g_w) {
            buf_g = dpdp.at(i-g_w) + g_val;
        }
        if (i >= s_w) {
            buf_s = dpdp.at(i-s_w) + s_val;
        }
        if (i >= b_w) {
            buf_b = dpdp.at(i-b_w) + b_val;
        }
        dpdp.at(i) = max(buf_g, max(buf_s, max(buf_b, dpdp.at(i-1))));
    }
    return dpdp.at(don);
}

int main () {
    int n, g_a, s_a, b_a, g_b, s_b, b_b;
    cin >> n >> g_a >> s_a >> b_a >> g_b >> s_b >> b_b;
    long long don = n;
    don += dp(don, g_b-g_a, g_a, s_b-s_a, s_a, b_b-b_a, b_a);
    don += dp(don, g_a-g_b, g_b, s_a-s_b, s_b, b_a-b_b, b_b);
    cout << don << endl;
    return 0;
}


Measured memory_bytes: 195584
#include<bits/stdc++.h>
#define x first
#define y second
#define size(a) (ll)(a).size()

typedef long long ll;
typedef long double ld;

using namespace std;
int n;
string s;


int main()
{
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");


    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> s;
    n = size(s);

    vector<int> Dp1(n, 0), Dp2(n, 0);
    Dp1[0] = 1;
    Dp2[0] = 0;

    for (int i = 0; i < n - 1; i++)
    {
        if (s[i + 1]  != s[i])
        {
            Dp1[i + 1] = Dp1[i] + 1;
        }

        Dp1[i + 1] = max(Dp1[i + 1], Dp2[i] + 1);

        if (i >= 2)
        {
            if (s[i - 2] != s[i] || s[i - 1] != s[i + 1])
            {
                Dp2[i + 1] = Dp2[i - 1] + 1;
            }
        }

        if (i >= 1)
        {
            Dp2[i + 1] = max(Dp2[i + 1], Dp1[i - 1] + 1);
        }
    }

    cout << max(Dp1[n - 1], Dp2[n - 1]) << "\n";

}


Measured memory_bytes: 2196
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
#include <tuple>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> pii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int64 n;
  cin >> n;
  cout << (n * (n - 1)) / 2 << '\n';
  return 0;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;

#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

int main(int argc, char **argv) {
	string s, t = "CODEFESTIVAL2016";
	cin >> s;
	int res = 0;
	REP(i, s.length()) if (s[i] != t[i]) ++res;
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
grid = [list(s for s in input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if grid[i][j] != "#":
            min_i = 0 if i == 0 else i - 1
            max_i = h if i == h - 1 else i + 2
            min_j = 0 if j == 0 else j - 1
            max_j = w if j == w - 1 else j + 2
            filter = sum(list(g[min_j: max_j] for g in grid[min_i: max_i]), [])

            grid[i][j] = str(filter.count("#"))

for g in grid:
    print("".join(g))

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

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    long double a{0};
    for(unsigned long i = 0, A; i < N; ++i){
        cin >> A;
        a += static_cast<long double>(1) / A;
    }
    cout << 1 / a << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ctime>
#include <sstream>
#define weewoo ios::sync_with_stdio(false);cin.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define ll long long
#define se second
#define fi first
#define ctoi(x) (x-'0')
#define pi (acos(-1))
#define llputin(a,n) for(int i=0;i<n;i++){ll x;cin >> x;a.push_back(x);}
#define iputin(a,n) for(int i=0;i<n;i++){int x;cin >> x;a.push_back(x);}

#define MOD ((ll) 1e9 + (ll) 7)
using namespace std;

ll pw(ll x,ll a){
    if(a==0)
        return 1;
    ll t = pw(x,a/2);
    if(a%2==0)
        return (t*t);
    else
        return (t*t*x);
}

bool prime(int x)
{
    if(x < 2) return false;
        for(int i=2; i<= sqrt(x); i++) {
            if ((x%i) == 0) return false;
        }
    return true;
}



int main()
{
    weewoo;
    vector<int>a;
    ll n;
    cin >> n;
    bool ok=1;
    for(int i=0;i<n;i++){
        ll x;cin >> x;
        if(x%2==0){
            if(x%5!=0&&x%3!=0)
                ok=0;
        }
    }
    if(ok)
        cout << "APPROVED" << endl;
    else
        cout << "DENIED" << endl;
    return 0;
}


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

string n;
int main(){
    cin >> n;
    int num = stoi(n);
    int S = 0;
    for(int i = 0; i < n.size(); ++i){
        S+= n[i]-'0';
    }
    cout << ((num%S) ? "No" : "Yes");
}

Measured memory_bytes: 256
import math
h,m,a,b=map(int,input().split())
if a>=12:
    a-=12
hour=360/12
hour_angle=hour*a+hour/60*b
minute=360/60
minute_angle=minute*b
ans=min(abs(minute_angle-hour_angle),360-abs(minute_angle-hour_angle))
print((h**2+m**2-2*h*m*math.cos(math.radians(ans)))**(1/2))

Measured memory_bytes: 9512
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, a, n) for(int i=a; i<n; i++)
#define ll long long
#define all(x) begin(x), end(x)
#define toInt(x) (x - '0')
#define pll pair<ll, ll>
#define pli pair<ll, int>
// #define int long long

#define INF 1e+9
#define MAX_V 100008


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

int main(){
  int n, m;
  vector<int> v(n);
  char s;
  cin >> s;
  // cout << s - 'a' << endl;
  if(0 <= s - 'a' && s - 'a' <= 25){
    cout << 'a' << endl;
  }else{
    cout << "A" << endl;
  }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int N;
string S;
int main() {
	cin >> N >> S;
	int r = 0;
	for (int i = 0; i < 1000; ++ i) {
		int n = i;
		int x = 0;
		for (int j = 0; j < N; ++ j) {
			if (S[j] == (n%10) + '0') {
				if (++ x == 3) {
					++ r;
					break;
				}
				n /= 10;
			}
		}
	}
	cout << r << endl;
}


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

int main() {
	// your code goes here
	int a,b,c;
	cin >> a >> b >> c;
	if(a==b){
		if(b!=c){
			cout << "Yes" << endl;
		}
		else cout << "No" << endl;
	}
	else if(a==c){
		cout << "Yes" << endl;
	}
	else if(b==c){
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
N, M = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(M)]


x = set()
for a, b in AB:
    if a == 1:
        x.add(b)
    if b == 1:
        x.add(a)

f = False

for a, b in AB:
    if (a in x and b == N) or (b in x and a == N):
        f = True

if f:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Measured memory_bytes: 45116
#include <bits/stdc++.h>
using namespace std;
using namespace std::literals::chrono_literals;
using namespace std::literals::string_literals;
using ll = long long;

#define repi(i, s, n) for (long long i {s}, i##_len{n}; i < i##_len; ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) std::begin(x), std::end(x)

namespace xmaho
{
inline namespace input
{
template<typename T>
T get_value(std::istream& is = std::cin);
template<typename C>
C get_container(std::istream& is = std::cin, typename C::size_type length = std::numeric_limits<typename C::size_type>::max());
}
}
namespace xmaho
{
inline namespace integer
{
template<typename C>
constexpr auto ssize(const C& c) noexcept(noexcept(c.size()))
  -> typename std::common_type<std::ptrdiff_t, typename std::make_signed<decltype(c.size())>::type>::type;
template <class T, ptrdiff_t N>
constexpr std::ptrdiff_t ssize(const T (&)[N]) noexcept;
}
}
using namespace xmaho;

int main()
{
  const auto a {get_value<ll>()};
  const auto b {get_value<ll>()};
  const auto k {get_value<ll>()};
  const auto a_left {k < a ? a - k : 0};
  const auto b_left {a_left != 0 ? b : k - a < b ? b - k + a : 0};
  cout << a_left << ' ' << b_left << '\n';
  return 0;
}

class initalization
{
  class custom_numpunct: public std::numpunct<char>
  {
  public:
    using numpunct::numpunct;
  protected:
    std::string do_truename() const override { return "Yes"; }
    std::string do_falsename() const override { return "No"; }
  };

public:
  initalization()
  {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.imbue(std::locale(std::cout.getloc(), new custom_numpunct{}));
    std::cout << std::boolalpha << std::fixed << std::setprecision(15);
  }
} initalize;

template<typename T>
T xmaho::input::get_value(std::istream& is)
{ T v {}; is >> v; return v; }

template<typename C>
C xmaho::input::get_container(std::istream& is, typename C::size_type length)
{
  C v {};
  if (length != std::numeric_limits<typename C::size_type>::max())
    v.reserve(length);
  typename C::value_type e {};
  for (auto i {length}; i != 0 && is >> e; --i)
    v.push_back(std::move_if_noexcept(e));
  return v;
}

template<typename C>
constexpr auto xmaho::integer::ssize(const C& c) noexcept(noexcept(c.size()))
  -> typename std::common_type<std::ptrdiff_t, typename std::make_signed<decltype(c.size())>::type>::type
{ return c.size(); }

template <class T, ptrdiff_t N>
constexpr std::ptrdiff_t xmaho::integer::ssize(const T (&)[N]) noexcept
{ return N; }


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

#define y1 ____

using namespace std;

typedef long long ll;

ll s, x1, x2, y1, y2;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> s;
	
	if(s == 1e18){
		x1 = 1e9; y2 = 1e9;
	}
	else{
		x1 = 1e9;
		y2 = s / x1 + 1;
		x2 = 1;
		y1 = x1 * y2 - s;
	}
	
	cout << "0 0 " << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
typedef long long ll;
using namespace std;

void solve(){
  int n, m, ans = 0; cin >> n >> m;
  vector<pair<int, int> > e(m);
  for(int i = 0; i < m; i++){
    cin >> e[i].first >> e[i].second;
  }
  for(int i = 0; i < m; i++){
    vector<vector<int> > v(n + 1);
    for(int j = 0; j < m; j++){
      if(j == i) continue;
      v[e[j].first].push_back(e[j].second);
      v[e[j].second].push_back(e[j].first);
    }
    queue<int> q;
    q.push(1);
    int cnt = 1;
    vector<bool> visited(n + 1, false);
    visited[1] = true;
    while(q.size() > 0){
      int c = q.front();
      q.pop();
      for(int j = 0; j < v[c].size(); j++){
        int nx = v[c][j];
        if(visited[nx] == false){
          q.push(nx);
          visited[nx] = true;
          cnt++;
        }
      }
    }
    if(cnt != n){
      ans++;
    }
  }
  cout << ans << endl;
  return;
}

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


Measured memory_bytes: 256
H,W=map(x->parse(Int,x),split(readline()))
N=parse(Int,readline())
A=map(x->parse(Int,x),split(readline()))
c=zeros(Int,H,W)
x=y=d=1
for i=1:N
  for j=1:A[i]
    c[x,y]=i
    y+=d
    if y<1||y>W
      y-=d
      x+=1
      d=-d
    end
  end
end
for i=1:H
  for j=1:W
    print(c[i,j],j==W?"\n":" ")
  end
end

Measured memory_bytes: 113536
#include <iostream>
#include <algorithm>

using namespace std;

/*Assumption:a > b*/
int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

/*c is gcd.*/
int lcm(int a, int b, int c) {
  return (a / c) * b;
}

int main() {
  int a, b, c;
  while(cin >> a >> b) {
    //    swap(a, b);
    c = gcd(a, b);
    cout << c << ' ' << lcm(a, b, c) << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <tuple>

using namespace std;

int main()
{  
    int N;
    cin >> N;
    vector<pair<string,pair<int, int>>> R(N);
    for(int i = 0; i < N; i++){
        cin >> R[i].first >> R[i].second.first;
        R[i].second.second = i + 1;
        R[i].second.first = R[i].second.first*-1;
    }
    sort(R.begin(), R.end());

    for(int i = 0; i < N; i++){
        cout << R[i].second.second << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;

#define MAX 100000

struct Node
{
	int parent; //??????????????????(???????????°-1)
	int left;   //??????????????????????????????
	int right;  //?????????????????????????????????
public:
	Node() { parent = left = right = -1; }
};

Node T[MAX];
int D[MAX]; //??????????????±???

void setDepth(int u, int p)
{
	D[u] = p;
	
	if (T[u].right != -1)
		setDepth(T[u].right, p);

	if (T[u].left != -1)
		setDepth(T[u].left, p + 1);
}

void show(int u)
{
	printf("node %d: ", u);
	printf("parent = %d, ", T[u].parent);
	printf("depth = %d, ", D[u]);

	if (T[u].parent == -1) printf("root");
	else if (T[u].left == -1) printf("leaf");
	else printf("internal node");
	
	printf(", [");
	int c = T[u].left;
	int flg = 0;
	while (c != -1) {
		if (flg) printf(", ");
		printf("%d", c);
		c = T[c].right;
		flg = 1;
	}
	printf("]\n");
}

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

	int id, k, c, l;
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &id, &k);
		for (int j = 0; j < k; j++) {
			scanf("%d", &c);
			if (j == 0) T[id].left = c;
			else T[l].right = c;
			l = c;
			T[c].parent = id;
		}
	}
	int r;
	for (int i = 0; i < n; i++) {
		if (T[i].parent == -1) {
			r = i;
			break;
		}
	}
	setDepth(r, 0);

	for (int i = 0; i < n; i++)
		show(i);
	return 0;		
}

Measured memory_bytes: 5720
class Num
  include Comparable
  @@count = 0
  @@sum_weight = 0
  attr_accessor :weight, :position, :right_position, :sum_weight
  def initialize(weight)
    @weight = weight
    @position = @@count
    @@count += 1
    @right_position = nil
  end
  
  def <=>(other)
    @weight <=> other.weight
  end
  
  def swap(other)
    #p [@weight, other.weight]
    @position, other.position = other.position, @position
    @@sum_weight += @weight + other.weight
  end
  
  def inspect
    #return [@weight, @position, @right_position]
    return @weight
  end
  
  def move(other)
    if self != other
      swap(other)
      return @position == @right_position
    else
      return true
    end
  end
  
  def self.sum_weight
    return @@sum_weight
  end
  
  def self.add(other)
    @@sum_weight += other
  end
end
class String
  def to_n
    return Num.new(self.to_i)
  end
end

def main
  gets
  arr = gets.split(" ").map(&:to_n)
  arr2 = arr.sort
  arr2.each_with_index{|item, idx|item.right_position = idx}
  arr2.each{|item|
    temp = 3 * arr2[0].weight + item.weight
    until item.move(arr2[item.position])
      temp -= item.weight - arr2[0].weight
    end
    if temp < 0
      Num.add(temp)
    end
    }
  puts Num.sum_weight
end
main

Measured memory_bytes: 6136
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
int main() {fio; // remove during scanf
    ll N, M;
    cin >> N >> M;
    string s, t;
    cin >> s >> t;
    ll lcm = (N * M) / __gcd(M, N);
    map <int, char> huh;
    for(int i = 0; i < N; i++) {
        int k = i * (lcm / N);
        huh[k] = s[i];
    }
    for(int j = 0; j < M; j++) {
        int k = j * lcm / M;
        if(huh.find(k) != huh.end()) {
            if(huh[k] != t[j]) {
                cout << -1;
                return 0;
            }
        }
    }
    cout << lcm;
    return 0;
}

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

#define oo 1000000000000000000LL
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define In insert
#define mod 1000000007
#define File(s) ifstream fin ((string)s + ".in", ios::in), ofstream fout ((string)s + ".out", ios::out);

using namespace std;

typedef long long int ll;
typedef long double ld;

const int N = 2e4 + 7;
ll a [1003], b[1003];
ll dp [N];

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

    ll i, j, r, n, h;

    for (i = 1; i < N; i++)
        dp[i] = oo;

    cin>> h >> n;
    for (i = 0; i < n; i++)
        cin>> a[i] >> b[i];

    for (i = 1; i < N; i++) {
        for (j = 0; j < n; j++) {
            if (i >= a[j]) {
                if (dp[i] > (dp[i - a[j]] + b[j])) {
                    dp[i] = (dp[i - a[j]] + b[j]);
                    for (r = i-a[j]; r < i; r++)
                        dp[r] = min (dp[r], dp[i]);
                }
            }
        }
    }

    cout<< dp[h] << endl;

    // cout<< "\naa\n";

    // for (i = 0; i < 12; i++)
    //     cout<< i << " " << dp[i] << endl;

    // cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
#include <stack>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>

#define ll long long
#define ld long double
#define endl '\n'
#define maxN 1000001
#define maxN 1000001
#define oo 1000000000000000001
#define Mod 1000000007
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define fi first
#define se second
#define sefi se.fi
#define sese se.se

#define pc putchar
#define gc getchar

using namespace std;
string s;
ll k;
bool flag[maxN];
ll l,r;
void Solve()
{
	fill_n(&flag[0],sizeof(flag)/sizeof(flag[0]),true);
	l=0;
	r=s.length();
	ll cnt=0;
	while(s[l+1]==s[0]&&l+1<r)
		l++;
	while(s[r-1]==s[0]&&r-1>l)
		r--;
	for(int i=l+1;i<r;i++)
	{
		if(s[i]==s[i-1]&&flag[i-1])
		{
			flag[i]=false;
			cnt++;
		}
	}
	//cout<<cnt<<" "<<l<<" "<<r<<endl;
	if(l==s.length()-1&&r==s.length())
	{
		cout<<s.length()*k/2;
	}
	else
		cout<<cnt*k+(l+1)/2+(s.length()-r)/2+(l+1+s.length()-r)/2*(k-1);
}
void Enter()
{
	cin>>s;
	cin>>k;
	//cout<<s<<k;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("/Users/quanghuy/Desktop/Input.inp","r", stdin);
    // freopen("/Users/quanghuy/Desktop/Output.out","w", stdout);
    //freopen("Input.inp","r",stdin);
    //freopen("Output.out","w",stdout);

	Enter();    
    Solve();
}



Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int N,M,X,Y,i;
    cin >> N >> M >> X >> Y;
    int x[N],y[M];
    for(i=0;i<N;i++){
        cin >> x[i];
    }
    for(i=0;i<M;i++){
        cin >> y[i];
    }
    sort(x,x+N);
    sort(y,y+M);
    if(x[N-1]<y[0]&&x[N-1]<Y&&X<y[0]){
        cout << "No War" << endl;
    }else{
        cout << "War" << endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
 
int main(void)
{
  int a;
  int sum=0;
  
  scanf("%d",&a);
  
  sum = (a / 500) * 1000;
  sum +=(a % 500) / 5 * 5;
  
  printf("%d",sum);
  
  return 0;
}

Measured memory_bytes: 128
// alds1_2_a bubble sort
#include <iostream>
using namespace std;

int cnt = 0;

void printline(int a[], int n, int cnt){
    // cout << cnt << " > " ;
    for(int i=0; i<n; i++){
        cout << a[i] ;
        if (i != n-1){ cout << " ";}
    }
    cout << endl;
}

void bubbleSort(int a[], int n){
    int flag = 1;
    int temp;
    while(flag){
        flag = 0;
        for(int j=n-1; j>0; j--){
            if(a[j] < a[j-1]){
                temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
                flag = 1;
                cnt++;

                // printline(a,n,cnt);
            }
        }
    }
    printline(a,n,cnt);
}



int main(){
    int i,n;
    int a[100];

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

    bubbleSort(a, n);
    
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3120