akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> P(n*n);
  rep(i, n*n) {
    cin >> P[i];
    P[i]--;
  }
  vector<int> cost(n*n);
  rep(i, n) rep(j, n) {
    cost[i*n+j] = min({i, n-1-i, j, n-1-j});
  }
  vector<bool> done(n*n);
  int dx[] = {-1, 0, 1, 0};
  int dy[] = {0, 1, 0, -1};
  auto bfs = [&](int p) {
    queue<int> q;
    int x = p / n;
    int y = p % n;
    rep(k, 4) {
      int nx = x + dx[k];
      int ny = y + dy[k];
      int ne = nx * n + ny;
      if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
      if(cost[ne] > cost[p]) {
        cost[ne] = cost[p];
        q.push(ne);
      }
    }
    vector<bool> vis(n*n);
    while(!q.empty()) {
      int cur = q.front(); q.pop();
      int x = cur / n;
      int y = cur % n;
      if(vis[cur]) continue;
      vis[cur] = true;
      rep(k, 4) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        int ne = nx * n + ny;
        if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if(cost[ne] > cost[cur] + !done[cur]) {
          cost[ne] = cost[cur] + !done[cur];
          q.push(ne);
        }
      }
    }
  };
  ll ans = 0;
  rep(i, n*n) {
    ans += cost[P[i]];
    done[P[i]] = true;
    bfs(P[i]);
  }
  cout << ans << endk;
  return 0;
}


Measured memory_bytes: 5288
#include<iostream>
#include<map>
main(){for(int A,N,i,a,f;std::cin>>A,f=i=A;f-A?printf("%d\n",a):puts("NO COLOR"))for(std::map<int,int>m;i-->0;++m[N]>A/2&&f++&(a=N))std::cin>>N;}

Measured memory_bytes: 1940
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    import math
    input = stdin.readline

    # import random

    n, k = map(int, input().split())
    ans = set(range(1, n+1))
    for _ in range(k):
        d = int(input())
        aa = set(map(int, input().split()))
        ans = ans-aa
    print(len(ans))


Measured memory_bytes: 9180
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) (a).begin(), (a).end()
#define AALL(a, n) (a), ((a) + (n))
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define MODNUM (INT(1e9 + 7))
#define MOD(x) ((x) % MODNUM)

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

const int INF = 2e9;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

template <typename T>
int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T>
void chmax(T& m, T x) {
	m = max(m, x);
}

template <typename T>
void chmin(T& m, T x) {
	m = min(m, x);
}

template <typename T>
T square(T x) {
	return x * x;
}

inline int toInt(string s) {
	int v;
	istringstream sin(s);
	sin >> v;
	return v;
}

int main() {
	int n;
	scanf("%d", &n);
	VI a(n);
	REP(i, n) { scanf("%d", &a[i]); }
	bool flag = true;
	REP(i, n) {
		if(a[i] % 2 == 0) {
			if(a[i] % 3 != 0 && a[i] % 5 != 0) {
				flag = false;
			}
		}
	}
	puts(flag ? "APPROVED" : "DENIED");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100001
typedef long long LL;

LL a[N];

LL read()
{
	char c;
	while((c = getchar()) < 48 || c > 57);
	LL x = c - 48;
	while((c = getchar()) > 47 && c < 58) x = x * 10 + c - 48;
	return x;
}

int main()
{		
	int n, i;
	LL m = 1000000000000000000, ans = 1;
		
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		if(!(a[i] = read())) ans = 0;
	}
	if(!ans) puts("0");
	else{
		for(i = 0; i < n; i++){
			m /= a[i];
			if(!m){
				ans = -1;
				break;
			}
			ans *= a[i];
		}
		printf("%lld\n", ans);
	}
		
			
	return 0;
}

Measured memory_bytes: 2492
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll MOD = (ll)1e9 + 7;
ll mult(ll x, ll y)
{
	return (x * y) % MOD;
}

typedef pair<int, int> pii;
#define mp make_pair

const int N = (int)1e6 + 4;
int n;
pii a[N];

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

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i].first);
		a[i].second = 1;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i + n].first);
		a[i + n].second = -1;
	}
	sort(a, a + 2 * n);
	ll ans = 1;
	int bal = 0;
	for (int i = 0; i < 2 * n; i++)
	{
		int x = a[i].second;
		if (bal > 0 && x < 0)
			ans = mult(ans, bal);
		if (bal < 0 && x > 0)
			ans = mult(ans, -bal);
		bal += x;
	}
	printf("%lld\n", ans);

	return 0;
}

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

int main(){
	long long a,b,c,k;
	long long kari;
	cin >> a >> b >> c >> k;

	if(k <= a){
		cout << k << endl;
	}else if(k <= a+b){
		cout << a << endl;
	}else{
		kari = k - a - b;
		cout << a - kari << endl;
	}
}


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

int main(){
    int ans=0,sum=0;
    int a,b,c,d;
    
    cin >>a>>b>>c>>d;
    

    for (int i = min(a,c); i < max(b,d); i++){
        if(max(a,c) <= i && i < min(b,d))ans++;
    }
    


    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=[int(i) for i in input().split()]
col=[0 for i in range(9)]
for a in A:
  if a<3200:
    col[a//400]+=1
  else:
    col[-1]+=1
ans=0
# print(col)
for i in range(8):
  if col[i]>0:
    ans+=1

MIN=1 if ans==0 else ans
MAX=ans+col[-1]
print(MIN,MAX)

Measured memory_bytes: 3064
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author ExplodingFreeze
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
#define int long long
#define f(i,a,b) for(int i=(a);i<(b);i++)
#define MOD 1000000007
using pii=std::pair<int,int>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); <-- PUT IN main()/solve()!

using namespace std;

int n,compatibility[25][25];
int dp[1<<(21)];
class OMatching {
public:
	void solve(std::istream& in, std::ostream& out) {
		in >> n;
		f(i,0,n)
			f(j,0,n)
				in >> compatibility[i][j];
		dp[0]=1;
		f(i,0,(1<<n))
		{
			if(dp[i]>=MOD)
				dp[i]%=MOD;
			int x=0;
			f(j,0,n)
				if(i&(1<<j))
					x++;
			f(j,0,n)
				if((!(i&(1<<j)))&&(compatibility[x][j]))
					dp[i|(1<<j)]+=dp[i];
		}
		//f(i,0,(1<<n))
			//out << dp[i] << "\n";
		out << dp[(1<<n)-1] << "\n";
	}
};


int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	OMatching solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 16640
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <string>

#define MAX 20000
using namespace std;



int main(){
   long n;
  std::cin >> n;
  unsigned long long a=1,b=2,c;
  while (n>1) {
    c=a;
    a=a+b;
    b=c;
    n--;
  }
  std::cout << a << '\n';
}


Measured memory_bytes: 256
#include<stdio.h>
int solve(int,int);
int n,A[2000];

int main() 
{
  int i,q,m;

  scanf("%d",&n);
  for(i=0; i<n; i++) 
    scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i=0; i<q; i++) {
    scanf("%d",&m);
    if(solve(0,m))
      printf("yes\n");
    else printf("no\n");
  }
  return 0;
}

int solve(int i,int m) 
{
  if(m==0) 
    return 1;
  if(i >= n)
    return 0;
  return solve(i+1,m) || solve(i+1,m-A[i]);
}

Measured memory_bytes: 580
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)

int main() {
	ll N, K; cin >> N >> K;
	ll C = 1;
	rep(i, 0, N) {
		C = ((2 * C >= C + K) ? C + K : 2 * C);
	}
	cout << C << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cstdlib>
#define range(i,a,b) for(int i = (a); i <= (b); i++)
#define rrange(i,a,b) for(int i = (a); i >= (b); i--)
#define rep(i,b) for(int i = 1; i <= (b); i++)
#define rrep(i,b) for(int i = (b); i >= 1; i--)
#define all(a) (a).begin(), (a).end()
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
typedef long long ll;
const int N=5e3+11,INF=~0u>>2;
struct Edge{int nxt,to;}edge[N];
int f[N],g[N][2],a[N],head[N],num_edge,n;
void add_edge(int from,int to){
	edge[++num_edge].nxt=head[from];
	edge[num_edge].to=to;
	head[from]=num_edge;
}
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
void dfs(int u){
	for(int i=head[u];i;i=edge[i].nxt) dfs(edge[i].to);
	int now=0,pre=1;
	g[0][now]=0;
	rep(i,a[u]) g[i][now]=INF;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		now^=1;pre^=1;
		range(j,0,a[u]) g[j][now]=INF;
		range(j,0,a[u]-a[v]) g[j+a[v]][now]=min(g[j+a[v]][now],g[j][pre]+f[v]);
		range(j,0,a[u]-f[v]) g[j+f[v]][now]=min(g[j+f[v]][now],g[j][pre]+a[v]);
	}
	f[u]=INF;
	range(i,0,a[u]) f[u]=min(f[u],g[i][now]);
} 
int main(){
//	freopen("ex.in","r",stdin);
	n=read();
	range(i,2,n){
		int tmp=read();
		add_edge(tmp,i);
	}
	rep(i,n) a[i]=read();
	dfs(1);
	rep(i,n) if(f[i]==INF){
		puts("IMPOSSIBLE");
		return 0;
	}
	puts("POSSIBLE");
	return 0;
}

Measured memory_bytes: 384
s=input()
from collections import defaultdict
d=defaultdict(int)
for c in s: 
  d[c]+=1
a,b,c=d["a"],d["b"],d["c"]
mx=max(a,b,c)
mn=min(a,b,c)
#a,b,c = map(lambda x:x-mn, [a,b,c])
if mx-mn >=2:
  print("NO")
else:
  print("YES")

Measured memory_bytes: 3444
import Data.Array

solve :: Int -> Int -> Mint
solve n k = fastSum $ map (\(i,a)->M i*a) $ assocs arr where
  arr = array (1, k) [ (i, M (div k i) ^ n - sum ext) |
    i <- [k, k-1 .. 1],
    let ext = [arr!(i*m) | m <- [2..div k i] ] ]

main = do
  [n, k] <- map read.words <$> getLine
  print $ solve n k

modulus = 10^9 + 7
newtype Mint = M Int
instance Enum Mint where
  toEnum a = M $ mod a modulus
  fromEnum (M a) = a
instance Num Mint where
  (M a) + (M b) = toEnum $ a + b
  (M a) * (M b) = toEnum $ a * b
  negate (M a) = toEnum $ negate a
  fromInteger = toEnum . fromInteger
  abs = id
  signum _ = M 1
instance Show Mint where
  show = show . fromEnum

fastSum :: [Mint] -> Mint
fastSum = toEnum . sum . map fromEnum

Measured memory_bytes: 17196
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8[:](i8,i8,i8[:])", cache=True)
def solve(N, K, A):
    for _ in range(min(41, K)):
        A_cumsum = np.zeros(shape=N, dtype=np.int64)
        for i in range(N):
            A_cumsum[max(0, i - A[i])] += 1
            b = i + A[i] + 1
            if N - 1 < b:
                pass
            else:
                A_cumsum[b] -= 1
        A = np.cumsum(A_cumsum)
    return A


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    ans = solve(N, K, A)

    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 128996
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
long long arr[105],n,sum,cap[105][105],maxflow,pre[105];

queue <pair<long long, long long> > q;
vector<long long> adj[105];
const long long inf = 1e18;
long long bfs(){
	while(!q.empty())q.pop();
	pre[0]=-2;
	q.push({0ll,inf});
	while(!q.empty()){
		long long cur  = q.front().fi;
		long long flow = q.front().se;
		q.pop();
		for(auto v: adj[cur]){
			// cout<<v<<' '<<cur<<' '<<cap[cur][v]<<endl;
			if(pre[v]==-1&&cap[cur][v]>0){
				pre[v]=cur;
				long long newflow = min(flow,cap[cur][v]);
				if(v==n+1)return newflow;
				q.push({v,newflow});
			}
		}
	}
	return 0;
}
int main(){
	cin>>n;
	for(long long i =1;i<=n;i++){
		cin>>arr[i];
		
		if(arr[i]>=0){
			adj[i].pb(n+1);
			adj[n+1].pb(i);
			cap[i][n+1]+=arr[i];
			sum+=arr[i];
		}
		if(arr[i]<0){
			adj[i].pb(0);
			adj[0].pb(i);
			cap[0][i]-=arr[i];
		}
		for(int j =2*i;j<=n;j+=i){
			adj[i].pb(j);
			adj[j].pb(i);
			cap[i][j]= inf;
		}
	}
	while(1){
		memset(pre,-1,sizeof(pre));
		long long add =bfs();
		if(add==0)break;
		maxflow+=add;
		long long cur = n+1;
		while(cur!=0){
			long long prev = pre[cur];
			cap[prev][cur]-=add;
			cap[cur][prev]+=add;
			cur=prev;
		}
	}
	// cout<<maxflow<<endl;
	cout<<sum-maxflow<<endl;

}

Measured memory_bytes: 3744
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

struct Edge {
  int dst;
  char c;
};

typedef vector<vector<Edge> > G;
const int N = 100005;
bool visited[N];

void bfs(const G &g, int s, vector<int> &v) {
  int n = g.size();
  REP(i,n) visited[i] = 0;
  queue<int> Q; Q.push(s);
  visited[s] = 1;
  while(!Q.empty()) {
    int now = Q.front(); Q.pop();
    v.push_back(now);
    FOR(it, g[now]) {
      if (it->c == 'N') continue;
      int dst = it->dst;
      if (!visited[dst]) {
        visited[dst] = 1;
        Q.push(dst);
      }
    }
  }
}

void bfs2(const G &g, const vector<int> &v, int *dist) {
  int n = g.size();
  REP(i,n) dist[i] = INF;
  queue<int> Q;
  FOR(it, v) {
    Q.push(*it);
    dist[*it] = 0;
  }
  while(!Q.empty()) {
    int now = Q.front(); Q.pop();
    FOR(it, g[now]) {
      if (it->c == 'L') continue;
      int dst = it->dst;
      if (dist[dst] == INF) {
        dist[dst] = dist[now] + 1;
        Q.push(dst);
      }
    }
  }
}

int dist1[N];
int dist2[N];
int dist3[N];

int main() {
  int T;
  cin >> T;
  while(T--) {
    int n, m;
    cin >> n >> m;
    int ns, ls;
    cin >> ns >> ls;
    G g(n+1);
    REP(i,m) {
      char c;
      int a,b;
      cin >> a >> b >> c;
      g[a].push_back((Edge){b,c});
      g[b].push_back((Edge){a,c});
    }
    vector<int> vA;             // レノンがいる場所から自由にいける場所
    vector<int> vB;             // 夏への扉から自由にいける場所
    bfs(g,ls,vA);
    bfs(g,0,vB);
    if (find(ALL(vA),0) != vA.end()) {
      cout << 0 << endl;
      continue;
    }
    bfs2(g,vA,dist1);
    bfs2(g,vB,dist2);
    bfs2(g,vector<int>(1,ns),dist3);
    int ans = INF;
    REP(i,n+1) {
      //cout << dist1[i] << " " << dist2[i] << " " << dist3[i] << endl;
      ans = min(ans, dist1[i]+dist2[i]+dist3[i]);
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 5972
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
 
#define fi first
#define se second
#define endl '\n'
#define MOD(n,k) ( (n % k) + k ) % k
#define isOn(S, j) (S & (1 << j) )
#define setBit(S, j) (S | (1 << j ) )
#define LSB(S) (S & (-S))
 
int main () {   
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    map<ll, ll> mp;

    ll n, a, res = 0;
    pair<ll,ll> pri, seg;

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

    auto it = mp.end();

    while (mp.begin() != it) {
        --it;
        if (it->se >= 4 && res == 0) {
            res = it->fi * it-> fi;
            break;
        }
        if (it->se >= 2) {
            if (res == 0)
                res = it->fi;
            else {
                res *= it->fi;
                break;
            }

        }
    }

    cout << res << endl;

    return 0;
}  

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int w, hh, n;
  cin >> w >> hh >> n;
  int h = 0, m = w, u = 0, s = hh;
  rep(i, 0, n) {
    int x, y, a;
    cin >> x >> y >> a;
    if(a == 1) {
      h = max(x, h);
    }else if(a == 2) {
      m = min(x, m);
    }else if(a == 3) {
      u = max(y, u);
    }else {
      s = min(y, s);
    }
  }
  if((s - u) * (m - h) <= 0 ||  s <= u || m <= h) {
    cout << 0 << endl;
  }else {
    cout << (s - u) * (m - h) << endl;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;

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

    ll N, K;
    cin >> N >> K;
    vector<ll> P(N), C(N);
    rep(i, N) {
        cin >> P[i];
        P[i]--;
    }

    rep(i, N) { cin >> C[i]; }

    ll ans = -INF;
    rep(i, N) {
        int s = i;
        ll sum = 0;
        ll ccnt = 0;
        while (1) {
            ccnt++;
            sum += C[s];
            s = P[s];
            if (s == i) {
                break;
            }
        }

        ll path = 0;
        ll cnt = 0;
        while (1) {
            cnt++;
            path += C[P[s]];
            if (cnt > K)
                break;
            int num = (K - cnt) / ccnt;
            ll score = path + max(0LL, sum) * num;
            ans = max(ans, score);

            s = P[s];
            if (s == i)
                break;
        }
    }
    cout << ans << endl;

    return 0;
}

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

#define int long long
#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define endl "\n"
#define ends " "
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
#define debugV(v) cerr << #v << ": [ "; for(int __ = 0; __ < v.size(); __++) cerr << v[__] << ((__ != v.size() - 1) ? ", " : ends); cerr << ']' << endl
#define debugVP(v) cerr << #v << ": [ "; for(int ___ = 0; ___ < v.size(); ___++) cerr << '{' << v[___].first << ", " << v[___].second << '}' << ((___ != v.size() - 1) ? ", " : ends); cerr << ']' << endl
#define debugA(a, n) cerr << #a << ": [ "; for(int ____ = 0; ____ < n; ____++) cerr << a[____] << ((____ != n - 1) ? ", " : ends); cerr << ']' << endl
#define print(args...) fprintf (stderr, args)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int INF = 1e9, MOD = INF + 7;

/////////////////////////////////////////////////////////////////////

const int N = 1e2 + 20, M = 1e3 + 20;

int w[N], v[N];
int dp[N][M * N];

int32_t main(){

    sync;

    int n, W, sum = 0; cin >> n >> W;
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i], sum += v[i];
    dp[0][0] = 0;
	for(int i = 1; i <= sum; i++) dp[0][i] = INF;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= sum; j++) {
    	dp[i][j] = dp[i - 1][j];
		if (j >= v[i]) dp[i][j] = min(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
    }
    for(int i = sum; i >= 0; i--) if (dp[n][i] <= W) die(i);

    return 0;
}

Measured memory_bytes: 98176
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define RFOR(i, a, b) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using vi = vector<int>;
using vd = vector<double>;
using i64 = int64_t;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> &v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

int main() {
  int n;
  cin >> n;
  vi c(n), v(n);
  REP(i, n) { cin >> v[i]; }
  REP(i, n) { cin >> c[i]; }
  int ans = 0;
  REP(i, n) {
    auto get = v[i] - c[i];
    if (get > 0) ans += get;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, n) for (int i = (a); i < (n); ++i)
using namespace std;
using ll = long long;
using uint = unsigned int;
const ll mod = (ll)1e9 + 7;

int c[26];
int s[365][26];

int cal_sat(int d, vector<int> &t) {
  int sat = 0;
  int last[26];
  rep(i, 26) last[i] = -1;
  rep(i, d) {
    sat += s[i][t[i]];
    last[t[i]] = i;
    rep(j, 26) sat -= c[j] * (i - last[j]);
    cout << sat << endl;
  }
  return sat;
}

int main() {
  int d;
  cin >> d;
  rep(i, 26) cin >> c[i];
  rep(i, d) rep(j, 26) cin >> s[i][j];
  vector<int> t(d);
  rep(i, d) {
    cin >> t[i];
    t[i]--;
  }
  int sat = cal_sat(d, t);
  //cout << sat << endl;
  return 0;
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    
    sort(all(data));

    if (data.back() - data[0] > 1) {
        std::cout << "No" << std::endl;
        return 0;
    }

    int sm = 0;
    rep(i, n) {
        if (data.back() != data[i]) sm++;
    }

    if ((data.back() - sm) == n-1 ||
            (data.back() - sm) <= (n - sm) / 2 && 0 < (data.back() - sm)) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}



Measured memory_bytes: 1024
//
//  main.cpp
//  procon
//
//  Created by ???????????? on 2015/05/21.
//  Copyright (c) 2015??´ y. inoue. All rights reserved.
//

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    while (true) {
        int N, M, P;
        cin >> N >> M >> P;
        if (!(N || M || P)) {
            break;
        }

        int pool = 0;
        int hit = 0;
        for (int i = 0; i < N; i++) {
            int num;
            cin >> num;
            pool += num;
            if (i == M - 1) {
                hit = num;
            }
        }

        if (hit == 0) {
            cout << 0 << "\n";
        } else {
            cout << pool * (100 - P) / hit << "\n";
        }
    }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define pp pair<ll,ll>
#define vi vector<ll>
#define f(i,a,b) for(ll i=a;i<b;i++)
#define r(i,b,a) for(ll i=b-1;i>=a;i--)
#define pq_min priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
#define pq_max priority_queue<pair<ll,ll>>
#define forx(i,a,b) for(ll i=a;i<b;i++)
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define fill(a,b) memset((a),(b),sizeof((a)))
#define ld long double
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
typedef pair<pp,pp> ppll;
const ll mod=998244353;
const ld pi = 3.14159265359;
const ll N=100005;

ll power(ll a,ll b)
{
    ll res=1;
    a%=mod;
    while(b>0)
    {
        if(b%2==1)
        {
            res = (res * a)%mod;
        }
        b/=2;
        a = (a*a)%mod;
    }
    return res;
}


int main()
{
  fast;
  ld n,m;
  cin>>n>>m;
  ld x=n*m;
  ll ans=floor(x);
  cout<<ans;
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;cin>>n;
    if (n>=10)
    {
        m=n%10;
    if(m==0||m==1||m==6||m==8)
        cout<<"pon";
    else if(m==2||m==4||m==5||m==7||m==9)
        cout<<"hon";
    else if(m==3)
        cout<<"bon";
    cout<<endl;
    }

   else{
    if(n==0||n==1||n==6||n==8)
        cout<<"pon";
    else if(n==2||n==4||n==5||n==7||n==9)
        cout<<"hon";
    else if(n==3)
        cout<<"bon";
    cout<<endl;}





}


Measured memory_bytes: 3632
n = input()

if n[-1] == "2" or n[-1] == "4" or n[-1] == "5" or n[-1] == "7" or n[-1] == "9":
    print("hon")
elif n[-1] == "0" or n[-1] == "1" or n[-1] == "6" or n[-1] == "8":
    print("pon")
else:
    print("bon")

Measured memory_bytes: 9116
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#define pi 3.14159265358979323846264338327950

int main() {
	long long H, W; std::cin >> H >> W;
	long long m = W * H;
	if (H == 1 || W == 1) {
		std::cout << 1 << std::endl;
		return 0;
	}
	if (H % 2 == 1 && W % 2 == 1)
		std::cout << m / 2 + 1 << std::endl;
	else
		std::cout << m / 2 << std::endl;

	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
typedef long long ll;

using namespace std;

int main () {
  string N;
  cin >> N;
  char c = N[0];
  bool f = true;
  for (int i = 1;i<N.size();i++) {
    if (c == N[i]) { cout << "Bad"; f = false; break; }
    c = N[i];
  }
  if (f) cout << "Good";
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  ll n,a,b;cin>>n>>a>>b;
  cout<<min(a,b)<<" "<<max(a+b-n,0LL)<<endl;
}

Measured memory_bytes: 256
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn print_edges(edges: &Vec<Vec<(usize, usize, usize)>>){
    let mut v = vec![];

    for i in 0..edges.len(){
        for j in 0..edges[i].len(){
            edges[i][j];
            v.push((edges[i][j].1, edges[i][j].2));
        }
    }

    v.sort();
    let num_color = v.iter().map(|x| x.1).max().unwrap();
    println!("{}", num_color);
    for elem in &v{
        println!("{}", elem.1);
    }
}


//                            node, order, color
fn solve(edges: &mut Vec<Vec<(usize, usize, usize)>>, cur_node: usize, used_color: usize){
    let mut next_color = 1;
    if used_color == next_color{
        next_color = 2;
    }

    for i in 0..edges[cur_node].len(){
        if edges[cur_node][i].2 == 0{
            edges[cur_node][i].2 = next_color;
            let next_node = edges[cur_node][i].0;
            solve(edges, next_node, next_color);
            //find next color
            next_color += 1;
            if used_color == next_color{
                next_color += 1;
            }
        }
    }
}

fn main(){
    let n = read_as_vec::<usize>()[0];

    let mut edges: Vec<Vec<(usize, usize, usize)>> = vec![vec![];n];
    for i in 0..n-1{
        let line = read_as_vec::<usize>();
        let (l, r) = (cmp::min(line[0]-1, line[1]-1),
                      cmp::max(line[0]-1, line[1]-1));

        edges[l].push((r, i, 0));
    }
    solve(&mut edges, 0, 0);

    let mut num_color = 2;
    for i in 0..edges.len(){
        num_color = cmp::max(num_color, edges[i].len());
    }

    print_edges(&edges);
}


Measured memory_bytes: 16764
s = str(input())
for i in range(len(s)):
  if i%2 == 0:
    if s[i] == 'R' or s[i] == 'U' or s[i] == 'D':
      continue
    else:
      print('No')
      exit()
  else:
    if s[i] == 'L' or s[i] == 'U' or s[i] == 'D':
      continue
    else:
      print('No')
      exit()
else:
  print('Yes')
    

Measured memory_bytes: 38384
cin = open(0).read().strip().split('\n')
h,w = map(int, cin[0].split(' '))
s = [list(a) for a in cin[1:]]

from collections import deque
q = deque()

dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0]=0

q.append((0,0))
while q:
    ph, pw = q.popleft()
    for dyi, dxi in zip([0,-1,0,1],[1,0,-1,0]):
        if 0<=ph+dyi<h and 0<=pw+dxi<w:
            if dist[ph+dyi][pw+dxi] != -1: continue
            if s[ph+dyi][pw+dxi] == '#': continue
            q.append((ph+dyi, pw+dxi))
            dist[ph+dyi][pw+dxi] = dist[ph][pw]+1

last = dist[h-1][w-1]
if last == -1:
    print(-1)
else:
    print(sum(s, []).count('.')-last-1)

Measured memory_bytes: 3444
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <deque>
#include <numeric>
using namespace std;

int main() {
    int N, Y;
    cin >> N >> Y;

    for (int i = 0; i <= N; i++) {
        for (int j = 0; i+j <= N; j++) {
            if (i * 10000 + j * 5000 + (N - i - j) * 1000 == Y) {
                cout << i << " " << j << " " << (N - i - j) << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    vector<ll> dp0(n+1);  /* dp0[i+1] : aおよびbの上からi桁目(iは0-index)までを確定させ、
                                         その時点ではまだa+bがs未満になるかわかっていない
                                         (a, b)の組の個数 */
    
    vector<ll> dp1(n+1);  /* dp1[i+1] : aおよびbの上からi桁目(iは0-index)までを確定させ、
                                         その時点で既にa+bがs未満であることがわかっている
                                         (a, b)の組の個数 */

    dp0[0] = 1;
    rep(i, n) {

        // (a_i, b_i) = (0, 0) の場合
        if(s[i] == '0') {
            dp0[i+1] = dp0[i];
            dp1[i+1] = dp1[i];
        }
        else if(s[i] == '1') {
            dp1[i+1] = dp0[i] + dp1[i];
        } 
        dp1[i+1] %= mod;
        
        // (a_i, b_i) = (0, 1), (1, 0) の場合
        if(s[i] == '0') {
            dp1[i+1] += 2*dp1[i];
        }
        else if(s[i] == '1') {
            dp0[i+1] += 2*dp0[i];
            dp1[i+1] += 2*dp1[i];
        }
        dp0[i+1] %= mod;
        dp1[i+1] %= mod;
    }

    cout << (dp0[n] + dp1[n])%mod << endl;
    return 0;
}

Measured memory_bytes: 2048
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

double solve(int n, double d, double x)
{
    double ans = d + x * (2 * n - 1) / 2;

    if(n > 1){
        double d2 = ((2 * n + 2) * d + 5 * x) / (2 * n);
        double x2 = ((2 * n + 4) * x) / (2 * n);
        ans += solve(n-1, d2, x2);
    }
    return ans;
}

int main()
{
    int n, d, x;
    cin >> n >> d >> x;

    printf("%.10f\n", solve(n, d, x));

    return 0;
}

Measured memory_bytes: 6528
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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










int main(){
    int N; std::cin >> N;
    std::vector<int> A(N), B(N), C(N+1), D(N+1), ans(N);
    for(int i(0); i < N; ++i){
        std::cin >> A[i]; ++C[A[i]];
    }
    for(int i(0); i < N; ++i){
        std::cin >> B[i]; ++D[B[i]];
    }
    for(int i(1); i <= N; ++i){
        C[i] += C[i-1]; D[i] += D[i-1];
    }

    int x(0);
    for(int i(1); i <= N; ++i){
        chmax(x, C[i] - D[i-1]);
    }
    for(int i(0); i < N; ++i){
        ans[i] = B[(i + N - x) % N];
        if(ans[i] == A[i]){
            std::cout << "No" << std::endl;
            return 0;
        }
    }
    std::cout << "Yes\n";
    for(int i(0); i < N; ++i){
        if(i) std::cout << " ";
        std::cout << ans[i];
    }
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 7220
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<string>
#include <stdlib.h>
#include <time.h>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    printf("%d\n",((n-m)*100+1900*m)*(1<<(m)));
}


Measured memory_bytes: 256
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # 下からc番目(0-indexed)の数
    # O(log(N))
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()
    
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))

bit = BITbisect(N)

for i in range(K):
    bit.insert(A[i]+1)

ans = 1
for i in range(K, N):
    if A[i-K]+1 != bit.search(0) or A[i]+1 <= bit.search(K-1):
        ans += 1
    bit.delete(A[i-K]+1)
    bit.insert(A[i]+1)

c = 1
p = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        c += 1
    else:
        if c >= K:
            p += 1
        c = 1
if c >= K:
    p += 1

ans -= max(p-1, 0)

print(ans)

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

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

    int A, B, C;
    std::cin >> A >> B >> C;

    int area = A * B / 2;
    std::cout << area << std::endl;
}


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

int main()
{
    int n;
    cin >> n;
    if (n > 17)
    {
        cout << "Yes";
        return 0;
    }
    else if (n == 4 || n == 7 || n == 8 || n == 11 || n == 12 || n == 14 || n == 15 || n == 16)
    {
        cout << "Yes";
        return 0;
    }
    else
    {
        cout << "No";
    }
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1e9+7
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
using namespace std;
void Bits (int a){
  string s="";
  while(a>0){
    char c='0'+a%2;
    a/=2;
    s+=c;
  }
  reverse(s.begin(),s.end());
  cout<<s<<endl;
}
int memo[70000];
int n;
int ans;
int dist[20][70000];
void dfs(int bits,int sum,int now){
  if(sum>=memo[bits])return;
  //Bits(bits);
  if(((1<<n)-1)==bits){
    ans=min(ans,sum);
    return;
  }
  memo[bits]=sum;
  for(int i=0;i<n;i++){
    if(!(bits&(1<<i))){
      int mimi=dist[i][0];
      for(int j=0;j<n;j++){
	if(bits&(1<<j))
	  mimi=min(dist[i][1<<j],mimi);
      }
      dfs(bits+(1<<i),sum+mimi,i);
    }
  }
  return;
}
int main(){
  while(cin>>n,n){
    ans=INF;
      for(int j=0;j<70000;j++)
	memo[j]=INF;
    for(int i=0;i<n;i++){
      cin>>dist[i][0];
      for(int j=0;j<n;j++)
	cin>>dist[i][(1<<j)];
    }
    for(int i=0;i<n;i++)
      dfs((1<<i),dist[i][0],i);
    cout<<ans<<endl;
  }
  return 0;
}




Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vi vector<ll>
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define pii pair<ll,ll>
#define vii vector<pii>
#define MOD 1000000007LL
#define calc_fact(n) tgamma(n+1)
#define INF LONG_LONG_MAX

signed main()
{
    FIO;
    ll n,a,sum=0,val1=0,val2=0,ans1=0,ans2=0;
    cin>>n;
    vi v;
    for(ll i=0;i<n;i++)
    {
        cin>>a;
        v.pb(a);
        sum+=a;
    }
    val1=ceil(((double)sum)/n);
    val2=floor(((double)sum)/n);
    for(auto it:v)
    {
        ans1+=(abs(val1-it)*abs(val1-it));
        ans2+=(abs(val2-it)*abs(val2-it));
    }
    cout<<min(ans1,ans2);
}

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

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int i[] = {sc.nextInt(),sc.nextInt(),sc.nextInt()};
        sc.close();
        Arrays.sort(i);
        String s = "";
        for(int j: i) s = s + j + " ";
        System.out.println(s.trim());
    }
}

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

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

  vector<int> A(N, 0);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A.at(i));
  }

  vector<int> ans(N, 0);
  for (int i = 0; i < N; i++) ans.at(A.at(i) - 1) = i + 1;
  for (int i = 0; i < N; i++) cout << ans.at(i) << " ";
  return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int A[3];
	REP(i, 3) cin >> A[i];
	int s = accumulate(A, A + 3, 0);
	puts(s >= 22 ? "bust" : "win");
	return 0;
}


Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n,l = readInts()
s = [input() for _ in range(n)]
s = sorted(s)
print(''.join(map(str,s)))


Measured memory_bytes: 10424
N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A in dic:
        dic[A] += B
    else:
        dic[A] = B


drink_num = 0
drink_cost = 0
for key, value in sorted(dic.items()):
    if drink_num + value >= M:
        drink_cost += (M - drink_num)*key
        break
    else:
        drink_cost += key*value
        drink_num += value

print(drink_cost)


Measured memory_bytes: 22992
import java.util.Scanner;

/**
 * Main
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        sc.close();

        int count = 0;
        while(N > 1000*count){
            count ++;
        }
        int ans = 1000*count - N;
        System.out.println(ans);
    }
}

Measured memory_bytes: 27080
#include<bits/stdc++.h>
#define int long long
using namespace std;
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; }


signed main()
{
    string s,t; cin>>s>>t;
    int N=s.size();
    int M=t.size();
                
    vector<vector<int> > dp(N+1,vector<int>(M+1));
    dp[0][0]=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(s[i]==t[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }else{
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }

    string ans="";
    int i=N;
    int j=M;
    while(i>0 and j>0){
        if(s[i-1]==t[j-1]){
            ans=s[i-1]+ans;
            i--; j--;
        }
        else{
            if(dp[i][j]==dp[i-1][j]){
                i--;
            }else{
                j--;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 70784
#include<bits/stdc++.h>
#define  p5         100005
#define  p6         1000007
#define  PI         acos(-1)
#define  M          1000000007
#define  sc         scanf
#define  ss         second
#define  ff         first
#define  pf         printf
#define  scin(x)    sc("%d",&x)
#define  scin2(x,y) sc("%d%d",&x,&y)
#define  READ(f)    freopen(f, "r", stdin)
#define  WRITE(f)   freopen(f, "w", stdout)
#define  ll         long long
#define  pp         pair < int, int>
#define  pq         priority_queue
#define  pb         push_back
#define OK          pf("Yes\n")
#define _OK         pf("No\n")
//int month[]={31,28,31,30,31,30,31,31,30,31,30,31};
//int dx[5] = {1, -1, 0, 0 };
//int dy[5] = {0, 0, 1, -1};
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    ll n,i,j,k;
    cin>>n;
    while(1)
    {
        for(i=2; i<n; i++)
        {
            if(n%i==0)
            {
                n++;
                break;
            }
        }
        if(i==n)
        {
            cout<<n<<endl;
            return 0;
        }
    }
    return 0;
}
//https://github.com/me-shaon/bangla-programming-resources


Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K = map(int, input().split())
V = list(map(int, input().split()))
lenV = len(V)

res = 0
for k in range(1, K+1):
    if lenV < k: break
    for rk in range(k+1):
        pick_list = V[:k-rk]
        if 0 < rk:
            pick_list.extend(V[-rk:])
        pick_list.sort()

        # remove negative number in pick_list
        not_neg_start_index = 0
        for i, num in enumerate(pick_list):
            if num < 0: continue
            else:
                not_neg_start_index = i
                break
        pos_sum = sum(pick_list[i:])
        neg_list = pick_list[:i]
        len_neg_list = len(neg_list)
        if K-k < len_neg_list:
            res = max(res, sum(neg_list[K-k:])+pos_sum)
        else:
            res = max(res, pos_sum)

print(res)

Measured memory_bytes: 41196
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<math.h>
#include<unordered_map>

using namespace std;
using ll = long long;
using vec = vector<int>;
using mat = vector<vec>;
using lst = list<int>;

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

bool solve()
{
	int t, n;
	cin >> t >> n;
	if (t == 0 && n == 0)return false;

	mat cell(200, vec(200, 0));

	for (int i = 0; i < n; ++i)
	{
		int x, y;
		cin >> x >> y;
		cell[x+100][y+100] = -1;
	}

	int bx, by; cin >> bx >> by;

	list<pair<int, int>> Q;
	Q.push_back({ bx+100, by+100 });
	cell[bx + 100][by + 100] = 1;
	int ans = 1;

	while (!Q.empty())
	{
		int x = Q.front().first, y = Q.front().second;
		for (int i = 0; i < 6; ++i)
		{
			if (cell[x + dx[i]][y + dy[i]] == 0)
			{
				ans++;
				cell[x + dx[i]][y + dy[i]] = 1 + cell[x][y];
				if (cell[x + dx[i]][y + dy[i]] <= t)
				{
					Q.push_back({ x + dx[i],y + dy[i] });
				}
			}
		}
		Q.pop_front();
	}
	cout << ans << endl;

	return true;
}

int main()
{
	while (solve());

	return 0;
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
int c, K;
void f(int i, int k, int p, int64_t n)
  {if (i >= k) {++c; if (c == K) {cout << n; exit(0);}}
  else for (int j : {-1, 0, 1}) if (0 <= p + j and p + j <= 9) f(i + 1, k, p + j, 10 * n + p + j);}
int main() {cin >> K; for (int k{1}; ; ++k) for (int p{1}; p <= 9; ++p) f(1, k, p, p);}

Measured memory_bytes: 3620