akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long lng;
#define UP(i,a,b) for(int i=(a); i<=(b); ++i)
#define DOWN(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) UP(i,0,n-1)
#define ALL(a) (a).begin(), (a).end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) //NOTE: <a> must be sorted in advance

lng power(lng b, lng n) {lng sol=1; while(n>0) {if(n&1) {sol=sol*b;} n>>=1; b*= b;} return sol;} //calculate b^n

const int MOD = 1000000007; //10^9+7


/*********** variables ************/

/**********************************/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    char c;
    cin >> c;
    char vo[] = {'a','i', 'u', 'e', 'o'};
    REP(i, 5) {
        if(c==vo[i]) {
            cout << "vowel" << endl;
            return 0;
        }
    }
    cout << "consonant" << endl;
}


Measured memory_bytes: 256
K = int(input())

if K%2 ==0 or K%5 == 0:
    ans = -1
else:
    det = 0
    num = 0
    cur = 0
    while True:
        num += 1
        cur += 7*pow(10,num-1,K)
        cur %= K
        #if num % 10000 == 0:
        #    print(num,cur)
        if cur == 0:
            ans = num
            break

print(ans)


Measured memory_bytes: 63332
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep2l(i, s, n) for (ll i = (ll)(s); i < (ll)n; i++)

int main() {
    int N, K, S;
    cin >> N >> K >> S;
    if (S < 1000000000) {
        rep(i, K) {
            cout << S << " ";
        }
        rep2(i, K, N) {
            if (i == N-1) {
                cout << S+1 << endl;
                return 0;
            }
            else {
                cout << S + 1 << " ";
            }
        }
    }
    else {
        rep(i, K) {
            cout << S << " ";
        }
        rep2(i, K, N) {
            if (i == N-1) {
                cout << 1 << endl;
            }
            else {
                cout << 1 << " ";
            }
        }
    }
}

Measured memory_bytes: 1280
from collections import deque
H,W=map(int,input().split())
G=[input() for i in range(H)]

b_n= [G[i].count("#") for i in range(H)]

root_min=float("inf")
root=deque([[0,0,1]])
F=[[0]*W for i in range(H)]
while len(root)!=0:
  p=root.popleft()
  if p[:2]==[H-1,W-1]:
    print(H*W-p[2]-sum(b_n))
    exit()
  F[p[0]][p[1]]=1
  for i in range(4):
    if i==0:
      n=[max(0,p[0]-1),p[1],p[2]+1]
    elif i==1:
      n=[min(H-1,p[0]+1),p[1],p[2]+1]
    elif i==2:
      n=[p[0],max(0,p[1]-1),p[2]+1]
    else:
      n=[p[0],min(W-1,p[1]+1),p[2]+1]
      
    if G[n[0]][n[1]]=="#":
      continue
    if F[n[0]][n[1]]==1:
      continue
    if n in root:
      continue
    root.append(n)
print(-1)

Measured memory_bytes: 43632
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define ios		ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
vi adj[100005];
vi v[100005];
int visited[100005]={0};
void dfs(int s,int cnt)
{
	visited[s]=1;
	v[cnt].pb(s);
	for(int i=0;i<adj[s].size();i++)
	{
		if(visited[adj[s][i]]==0)
		dfs(adj[s][i],cnt);
	}
}
int main()
{
	ios
	int n,m;
	cin>>n>>m;
	int a[n+1];
	map<int,int> m1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		m1[i]=a[i];
	}
	
	int x,y;
	

	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(visited[i]==0)
		{
			cnt++;
			dfs(i,cnt);
		}
	}

	for(int i=1;i<=cnt;i++)
	sort(all(v[i]));

	int ans=0;
	for(int i=1;i<=cnt;i++)
	{
		for(int j=0;j<v[i].size();j++)
		{
			if(bs(all(v[i]),m1[v[i][j]]))
			ans++;
		}
	}

	cout<<ans;
}

Measured memory_bytes: 18684
from math import sqrt

def factors(n):
    N = n
    prime_dict = {}
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            prime_dict[i] = 1
            n //= i
            while n % i == 0:
                prime_dict[i] += 1
                n //= i
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict

def factorial(n):
    if n == 1:
        return 1
    else:
        prime_set,prime_dict = set(),{}
        for i in range(2,n+1):
            F = factors(i)
            for fa in F:
                if fa not in prime_set:
                    prime_set.add(fa)
                    prime_dict[fa] = F[fa]
                else:
                    prime_dict[fa] += F[fa]

        output,M = 1,10**9+7
        for pr in prime_dict:
            output *= (prime_dict[pr]+1)
            output %= M
        return output

def main():
    N = int(input())

    print(factorial(N))

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
function myin(){return require("fs").readFileSync("/dev/stdin", "utf8").trim();}
function myout(t){console.log(t);}//standard output
function myerr(t){console.error(t);}//standard error
//[no]param
//0:何もしない  1:数値へ変換  2:半角SPで分割  3:改行で分割  4:半角SPで分割し、数値配列へ
//5:改行で分割し、数値配列へ  6:1文字に分割  7:1文字に分割し、数値配列へ
function myconv(i,no){switch(no){case 0:return i;case 1:return parseInt(i);case 2:return i.split(" ");case 3:return i.split("\n");case 4:return i.split(" ").map((a)=>Number(a));case 5:return i.split("\n").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));}}
function Main(input) {
  input = myconv(input,3);
  var N = myconv(input[0],4)[0];
  var x = myconv(input[0],4)[1];
  var list = myconv(input[1],4);
  list.sort(function(a,b){
  	return a-b;
  });
  var output = 0;
  for(var i = 0; i < N; i++){
    if(i == N -1){
      if(x == list[i]){ 
      	output++;
      }
    }else if(x >= list[i]){
       output++;
      x -= list[i];
    }
  }
  myout(output);
}
Main(myin());

Measured memory_bytes: 7500
#include <iostream>
#include <vector>
using namespace std;
int main() {
	long long n; cin >> n;
	vector<long long> a(n);
	for (long long i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<vector<long long> > dp(n, vector<long long>(n));
	for (long long i = 0; i < n; i++) {
		if (n % 2 == 0) {
			dp[i][i] = -a[i];
		} else {
			dp[i][i] = a[i];
		}
	}
	for (long long len = 2; len <= n; len++) {
		for (long long l = 0; l + len - 1 < n; l++) {
			long long r = l + len - 1;
			if (len % 2 == n % 2) {
				dp[l][r] = max(a[l] + dp[l + 1][r], a[r] + dp[l][r - 1]);
			} else {
				dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r]);
			}
		}
	}
	cout << dp[0][n - 1] ;
	return 0;
}

Measured memory_bytes: 73632
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <time.h>
#pragma comment (linker, "/STACK:200000000")
#define ll long long
#define mod 1000000007ll
#define maxn 1000000ll
using namespace std;


//fstream cin("input.txt"); ofstream cout("output.txt");
//fstream cin("hobby.in"); ofstream cout("hobby.out");
ll gcd(ll a, ll b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		ans += (r - l) + 1;
	}
	cout << ans;
	return 0;
}

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

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

int MOD=1e9+7;
ll INF=1e18;

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

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

    int m=n/2;
    if(n % 2 == 0) m--;

    int ans=0;
    for(int i=0; i<n; i++){
        if(i <= m){
            if(s[i] == 'p') ans--;
        }
        else{
            if(s[i] == 'g') ans++;
        }
    }
    cout << ans << endl;
}

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

int main() {
    int n, m;
    cin >> n;
    unordered_map<int, int> d;
    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        d[temp]++;
    }

    bool ret = true;
    cin >> m;
    for (int i = 0; i < m; i++){
        int diff;
        cin >> diff;

        if (d[diff] == 0){
            ret = false;
            break;
        }
        else{
            d[diff]--;
        }
    }

    if (ret){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

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

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 51;

int n;
int d, s = 0;

int res = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for1(i, n)
    {
        cin >> d;
        res -= d * d;
        s += d;
    }
    res += s * s;
    cout << res / 2;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

const int maxn = 1e5 + 10;

ll fact[maxn], fact_inv[maxn];

ll power(ll a, ll b) {
	ll result = 1;
	while(b) {
		if(b % 2) result = (result * a) % P;
		a = (a * a) % P;
		b /= 2;
	}
	
	return result;
}

ll divide(ll a, ll b) {
	return a * power(b, P - 2) % P;
}

ll C(ll n, ll k) {
	if(n < k) return 0;
	return ((fact[n] * fact_inv[k]) % P * fact_inv[n - k] % P);
}

void init() {
	fact[0] = 1;
	for(int i = 1; i < maxn; i++) fact[i] = (fact[i - 1] * i) % P;
	
	fact_inv[maxn - 1] = divide(1, fact[maxn - 1]);
	for(int i = maxn - 2; i >= 0; i--) fact_inv[i] = (fact_inv[i + 1] * (i + 1)) % P;
}

void solve() {
	int n;
	cin >> n;
	
	vi a(n + 1);
	for(int i = 0; i < n + 1; i++) cin >> a[i];
	
	int cnt;
	vi seen(n + 1, -1);
	for(int i = 0; i < n + 1; i++) {
		if(seen[a[i]] != -1) {
			cnt = seen[a[i]] + n - i;
			break;
		} else seen[a[i]] = i;
	} 
	
	cout << n << endl;
	for(int k = 2; k <= n + 1; k++) {
		ll ans = 0;
		ans += C(n + 1, k);
		ans %= P;
		ans = (ans - C(cnt, k - 1) + P) % P;
		
		cout << ans << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	init();
	solve();
    return 0;
}	

Measured memory_bytes: 5484
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int K, X;
  cin >> K >> X;
  for (int i = X - K + 1; i <= X + K - 1; i++)
    cout << i << (i == X + K - 1 ? '\n' : ' ');
  return 0;
}


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

int main() {
  string s, t;
  cin >> s >> t;
  vector<int> vec(s.size() - t.size() + 1);
  for (int i = 0; i < s.size() - t.size() + 1; i++){
    int count = 0;
    for (int j = 0; j < t.size(); j++){
      if (s.at(i + j) != t.at(j)){
        count++;
      }
    }
    vec.at(i) = count;
  }
  sort(vec.begin(), vec.end());
  cout << vec.at(0) << endl;
}




Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string s;
	cin >> s;
	ll sum = 0;
	int q;
	string x = "+";
	ll n = s.size() - 1;
	for(ll i = 0; i < (1<< n); i++) {
		string tmp = s;
		ll count = 1;
		for(ll j = 0; j <= n; j++) {
			if (i >> j & 1){
				tmp.insert(j+count,x);
				count++;
			}
		}


		string a = "";

		for(int k = 0; k < tmp.size(); k++) {
			if (tmp[k] != '+'){
				a += tmp[k];
			}
			else{
				q = a.size() - 1;
				while(q >= 0){
					sum += (a[q] - '0')*ll(pow(10,a.size() - 1 - q));
					q --;
				}
				a = "";
			}
			if (k == tmp.size() - 1 && tmp[k] != '+'){
				q = a.size() - 1;
				while(q >= 0){
					sum += (a[q] - '0')*ll(pow(10,a.size() - 1 - q));
					q --;
				}
			}
		}
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, ans = 0;
    string s;
    cin >> n >> s;
    char ch = '#';

    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] != ch){
            ans++;
        }
        ch = s[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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

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

vector<int> IntegerToVector(int bit, int N)
{
    vector<int> S;
    for (int i = 0; i < N; ++i)
    {
        if (bit & (1 << i))
        {
            S.push_back(i);
        }
    }
    return S;
}

int main()
{
    int n, q;
    cin >> n;
    int a[n];
    rep(i, n)
    {
        cin >> a[i];
    }

    set<int> s;
    for (int bit = 0; bit < (1 << n); ++bit)
    {
        vector<int> S = IntegerToVector(bit, n);
        int sum = 0;
        for (int i : S)
            sum += a[i];

        s.insert(sum);
    }

    cin >> q;
    rep(i, q)
    {
        int qq;
        cin >> qq;
        if (s.find(qq) != s.end())
            cout << "yes" << endl;
        else
        {
            cout << "no" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3152
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int pre = 0;
	int ans = 0;
	REP(i, N){
		int n;
		cin >> n;
		if (pre < n)ans += n - pre;
		pre = n;
	}
	cout << ans << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

LL e[25][25] = {0};
LL W[1 << 16] = {0};
LL dp[1 << 16][25] = {0};
LL n,m,tot = 0;

int main(){
	cin >> n >> m;
	for(LL i = 1;i <= m;i ++){
		LL u,v,w;
		cin >> u >> v >> w;
		e[u][v] = w;
		e[v][u] = w;
		tot += w;
	}
	for(LL S = 0;S < (1LL << n);S ++){
		for(LL i = 1;i <= n;i ++){
			for(LL j = i + 1;j <= n;j ++){
				if(((S >> (i - 1)) & 1) && ((S >> (j - 1)) & 1)) W[S] += e[i][j];
			}
		}
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[1][1] = 0;
	for(LL S = 0;S < (1LL << n);S ++){
		for(LL u = 1;u <= n;u ++){
			if(!((S >> (u - 1)) & 1)) continue;
			for(LL v = 1;v <= n;v ++){
				if((S >> (v - 1)) & 1) continue;
				if(!e[u][v]) continue;
				dp[S | (1 << (v - 1))][v] = max(dp[S | (1 << (v - 1))][v],dp[S][u] + e[u][v]);
			}
			LL U = ((1LL << n) - 1) ^ S;
			for(LL T = U;T;T = (U & (T - 1))){
				dp[S | T][u] = max(dp[S | T][u],dp[S][u] + W[T | (1 << (u - 1))]);
			}
		}
	}
	cout << tot - dp[(1LL << n) - 1][n] << endl;
	return 0;
}

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

typedef long long ll;
struct edge {ll to;ll cost;};
const int nmax = 100000;
vector<edge> g[nmax+2];
bool used[nmax+2];
vector<ll> dist(nmax+2);
void dfs(ll s, ll d) {
  if(used[s]) return;
  dist[s] = d;
  used[s] = true;
  for(int i=0;i<g[s].size();i++) {
    //if(used[g[s][i].to]) continue;
    dfs(g[s][i].to, d+g[s][i].cost);
  }
}
int main() {
  ll n;
  cin >> n;

  for(int i=0;i<n-1;i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;b--;
    edge e1 = {a, c}, e2 = {b, c};
    g[b].push_back(e1);
    g[a].push_back(e2);
  }
  ll q, k;
  cin >> q >> k;
  k--;
  //kからの最短距離
  for(int i=0;i<nmax;i++) used[i] = false;
  dfs(k, 0);
  vector<int> x(q), y(q);
  for(int i=0;i<q;i++) {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
  }

  for(int i=0;i<q;i++) {
    cout << dist[x[i]] + dist[y[i]] << endl;
  }

}


Measured memory_bytes: 15232
import sys
N, M = map(int, input().split())
S = input()
S = list(reversed(S))

position = 0
count = 0
answer = []
while True:
    for i in range(M, -1, -1):
        if i == 0:
            print(-1)
            sys.exit()
        if position + i > N:
            continue
        if S[position + i] == '0':
            answer.append(i)
            position += i
            break
    if position >= N:
        break
for i in reversed(answer):
    print(i)


Measured memory_bytes: 5536
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
#sort = sorted(a)[::-1] 降順
n = int(input())
a = list(map(int, input().split()))
flag = 0 #0:購入フェーズ　1:売却フェーズ
money = 1000
stock = 0

for k in range(len(a)-1):
    #購入
    if flag == 0:
        if a[k] < a[k+1]:
            stock = int(money / a[k])
            money = money - (a[k] * stock)
            flag = 1

    else:
        if a[k] > a[k+1]:
            money += stock * a[k]
            stock = 0
            flag = 0

k += 1
if flag == 1:
    money += stock * a[k]

print(money)


Measured memory_bytes: 9196
//============================================================================
// Name        : JOI.cpp
// Author      :2015 ho3
// Version     :???11:08
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int N,M,Q;
typedef pair<int,int> P;
int U[200001];
int V[200001];
int UV[200001]={};

vector<int> C[100001];
vector<int> C2[100001];
int R[200001];
int dp[100001]={};
int man[100001]={};
const int INF=10000000;

int main() {
	cin>>N>>M>>Q;

	for(int i=1;i<M+1;++i){
		cin>>U[i]>>V[i];
		C[U[i]].push_back(i);
		C[V[i]].push_back(i);
	}
	for(int i=0;i<Q;++i)cin>>R[i];
	for(int i=2;i<N+1;++i)dp[i]=INF;

	priority_queue<P,vector<P>,greater<P>> que;
	que.push(P(0,1));
	P p1;
	int cost,to,to2;
	while(que.size()){
		p1=que.top();que.pop();
		cost=p1.first;
		to=p1.second;
		if(cost>dp[to])continue;
		dp[to]=cost;
		for(auto it:C[to]){
			to2=U[it];
			if(to2==to)to2=V[it];
			if(cost+1<dp[to2]){
				que.push(P(cost+1,to2));
				dp[to2]=cost+1;
			}
		}
	}
	for(int i=2;i<N+1;++i){
		for(auto it:C[i]){
			if(dp[i]>dp[V[it]])C2[i].push_back(it);
			if(dp[i]>dp[U[it]])C2[i].push_back(it);
		}
	}

	int total=0;
	int sum,flg;
	man[1]=1;
	queue<int> que2;
	for(int i=0;i<Q;++i){
		sum=0;
		UV[R[i]]=1;
		to=V[R[i]];
		to2=U[R[i]];
		que2.push(to);
		que2.push(to2);

		while(que2.size()){
			to=que2.front();que2.pop();
			flg=0;
			if(man[to]>0)continue;
			for(auto it:C2[to]){
				to2=U[it];
				if(to2==to)to2=V[it];
				if(dp[to2]+1+UV[it]<=dp[to]){
					flg=1;
					break;
				}
			}

			if(flg==0&&to>1){
				if(man[to]==0){
					man[to]=1;
					sum+=1;
				}
				for(auto it:C[to]){
					to2=U[it];
					if(to2==to)to2=V[it];
					if(man[to2]==0)que2.push(to2);
				}
				dp[to]+=1;
			}
		}
		total+=sum;
		cout<<total<<endl;
	}
	return 0;
}

Measured memory_bytes: 18788
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n;
	cin>>n;
	int x[100], y[100], h[100];
	int i0;
	for(int i=0; i<n; i++){
		cin>>x[i]>>y[i]>>h[i];
		if(h[i]>0) i0=i;
	}
	for(int cx=0; cx<=100; cx++){
		for(int cy=0; cy<=100; cy++){
			int H=h[i0]+abs(x[i0]-cx)+abs(y[i0]-cy);
			bool nuee=0;
			for(int i=0; i<n; i++){
				if(max(0, H-abs(x[i]-cx)-abs(y[i]-cy))!=h[i]){
					nuee=1;
					break;
				}
			}
			if(!nuee){
				cout<<cx<<" "<<cy<<" "<<H<<endl;
				return 0;
			}
		}
	}
	return 0;
}

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

namespace AtCoder {
    class Program {
        static void Main(string[] args) {
            var input = IntInput(' ');
            if(input[0] == input[1]) {
                Output("Yes");
            } else {
                Output("No");
            }
        }

        #region ReadLineメソッド
        /// <summary>
        /// 文字列をリストで返す
        /// </summary>
        static List<string> StringInput(char splitChar) {
            return Console.ReadLine().Split(splitChar).ToList();
        }

        /// <summary>
        /// 文字列を分割し、数字のリストで返す
        /// </summary>
        static List<int> IntInput(char splitChar) {
            return StringInput(splitChar).Select(str => int.Parse(str)).ToList();
        }

        /// <summary>
        /// 数字を1つ返す
        /// </summary>
        static int IntInput() {
            return int.Parse(Console.ReadLine());
        }
        #endregion

        #region　WriteLineメソッド
        /// <summary>
        /// string型を改行せずに出力する
        /// </summary>
        static void Output(string str) {
            Console.Write(str);
        }

        /// <summary>
        /// int型をそのまま出力する
        /// </summary>
        static void Output(int number) {
            Console.WriteLine(number);
        }

        /// <summary>
        /// int型のリストを改行して出力する
        /// </summary>
        static void Output(List<int> numList) {
            numList.ForEach(num => Console.WriteLine(num));
        }
        #endregion 
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<set>
using namespace std;
int main(){
  set<int>way;
  way.insert(1);
  way.insert(2);
  int a,b;
  while(cin>>a>>b){
    if(!a){
      if(way.empty())cout<<"OK"<<endl;else cout<<"NG"<<endl;
      way.clear();
      way.insert(1);
      way.insert(2);
      continue;
    }
    if(way.find(a)==way.end())way.insert(a);else way.erase(a);
    if(way.find(b)==way.end())way.insert(b);else way.erase(b);
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, K; cin >> N >> K;
  bool have[N];
  for(int i = 0; i < N; i++) have[i] = false;
  int d, A;
  for(int i = 0; i < K; i++){
    cin >> d;
    for(int j = 0; j < d; j++){
      cin >> A;
      if(have[A - 1] == false) have[A - 1] = true;
    }
  }
  int ans = 0;
  for(int i = 0; i < N; i++){
    if(!have[i]) ans += 1;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3592
#include<algorithm>
#include<iostream>
#include<functional>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
  int n,ans[110],count=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>ans[i];
  }
  for(int j=1;j<n;j++){
    if(ans[j-1]==ans[j]){
      count++;
      ans[j]=0;
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i++)
#define all(cont) cont.begin(), cont.end()
#define unique(a)  sort(all(a)) , (a).erase(unique((a).begin(), (a).end()),(a).end())
#define rall(cont) cont.rbegin(), cont.rend()
#define sz(x) (int)(x).size()
#define fastio          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define PB push_back
#define endl "\n"
#define f first
#define s second
#define mset(m,v) memset(m,v,sizeof(m))
#define mod 1000000007
const int N = 2e5 + 5;
#define PI acos(-1.0)
long double EPS = 1e-9;
typedef long long ll;
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
#define pqll_max priority_queue<ll> // max heap. push(),pop(),top(),size(),empty()
#define pqll_min priority_queue<ll,vector<ll>,greater<ll> >
#define lb(v,val)   lower_bound(v.begin(),v.end(),val) //first equal to or lower than [------------
#define ub(v,val)   upper_bound(v.begin(),v.end(),val) //first greater than ------------)
#define bs(v,x) binary_search(v.begin(),v.end(),x)
inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x; }
inline ll sub(int x, int y) { x -= y; if (x < 0) x += mod; return x; }
inline ll mul(ll x, ll y) { return (x%mod * 1ll * y%mod) % mod; }
inline ll pwr(ll a, ll b) { ll x = 1 % mod; while (b) { if (b & 1) x = mul(x, a); a = mul(a, a); b >>= 1; }return x % mod; }
inline ll inv(ll a) { return pwr(a, mod - 2) % mod; }
ll gcd(ll a, ll b) { if (!a)return b % mod; return gcd(b%a, a) % mod; }
#define debug(x) cout << #x << " = " << x << endl;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#define in(container) for (auto &it : container) cin>>it;
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
void solve() {
	int x;
	cin >> x;
	int b = x % 10;
	if(b ==2 || b==4 || b==5 || b==7 || b==9){
		cout << "hon" << endl;

	}
	else if(b==3) {
		cout << "bon" << endl;
	}
	else{
	cout<<"pon"<<endl;
	}
}
signed main()
{
	fastio;
	//cout<<fixed<<setprecision(15);
	//clock_t begin = clock();
	int tc;
	tc = 1;
	//cin >> tc;
	while (tc--) {
		solve();
	}
	//clock_t end = clock();double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;cerr << elapsed_secs;
}


//Error?
// clear lists for every test case
// print new line for each tc
// check for int or ll
// check if problem can be solved without any heavy DS like priority_queue or map



Measured memory_bytes: 3640
#include <stdio.h>
#include <algorithm>
using namespace std;

int N; pair<int, int> P[2020];
long long D[2020][2020];

int main()
{
	scanf ("%d", &N);
	for (int i = 0; i < N; i++) scanf ("%d", &P[i].first), P[i].second = i;
	sort(P, P + N);
	reverse(P, P + N);

	for (int i = 0; i < N; i++) for (int j = 0; i + j < N; j++){
		int k = i + j;
		D[i + 1][j] = max(D[i + 1][j], D[i][j] + 1ll * P[k].first * abs(P[k].second - i));
		D[i][j + 1] = max(D[i][j + 1], D[i][j] + 1ll * P[k].first * abs(P[k].second - (N - 1 - j)));
	}

	long long a = 0;
	for (int i = 0; i <= N; i++){
		a = max(a, D[i][N - i]);
	}
	printf ("%lld\n", a);

	return 0;
}

Measured memory_bytes: 24420
#include<bits/stdc++.h>
using namespace std;
#define ran 111111
char A[ran],B[ran];
int n,m,a[ran],b[ran];
int main(){
	scanf("%s%s",A,B);
	n = strlen(A);
	m = strlen(B);
	int ss = 'A' - 1;
	for(int i=1; i<=n; i++)
		a[i] = a[i-1] + A[i-1] - ss;
	for(int i=1; i<=m; i++)
		b[i] = b[i-1] + B[i-1] - ss;
	int q,x,y,z,w;
	for(scanf("%d",&q); q--;){
		scanf("%d%d%d%d",&x,&y,&z,&w);
		puts((a[y]-a[x-1])%3 == (b[w]-b[z-1])%3?"YES":"NO");
	}
	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

#define REP(i,n) for(int i=0; i<n; i++)
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
 
#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9

using namespace std;
typedef long long ll;

int main(){
	while(1){
		int n, b[42], x1, x2, h;
		double ans, r;
		
		cin >> r >> n;
		if (r==0 && n==0) break;
		REP(i,42) b[i] = 0;
		
		for (int i=0; i<n; i++){
			cin >> x1 >> x2 >> h;
			for (int j=x1+20; j<x2+20; j++){
				b[j] = max(b[j], h);
			}
		}
		
		ans = (double)INF;
		for (int i=20-r; i<20+r; i++){
			int t = i - 20 + (i < 20);
			//cerr << r-sqrt(r*r-t*t) << endl;
			ans = min(ans, (double)(r-sqrt(r*r-t*t)+b[i]));
		}
		
		printf("%.4f\n", ans);
		
	}
	return 0;
}



Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()

typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
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 (b<a) { a=b; return 1; } return 0; }
//#define int long long


inline void solve(){
    string s;
    ll k;
    cin >>s >> k;
    int c=0;
    int i;
    for(i = 0; i < s.size() && i < k; i++){
        if(s[i]!='1'){
            c = i;
            break;
        }
    }
    cout << s[c] << endl;
    
}

struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;signed main(){solve();return 0;}



Measured memory_bytes: 508
//***Because people who are crazy enough to think that they can change the world are the ones who do it***
//Think different
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main(){
  ll l,r,d;
  cin>>l>>r>>d;
  cout<<(r/d)-(l-1)/d;
}

Measured memory_bytes: 3592
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

A=int(input())
B=int(input())
A2=min(A,B)
B2=max(A,B)
if(A2==1 and B2==2):
    print(3)
    sys.exit(0)

if(A2==2 and B2==3):
    print(1)
    sys.exit(0)

if(A2==1 and B2==3):
    print(2)
    sys.exit(0)


Measured memory_bytes: 5560
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>

int a,b,c;
int main(){
	cin>>a>>b>>c;
	if(a==b&&b!=c||a==c&&b!=c||b==c&&a!=b)puts("Yes");
	else puts("No");
    return 0;
}

Measured memory_bytes: 256
S = str(input())
T = str(input())
m = len(S)

for i in range(len(S) - len(T) + 1):
    x = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            x += 1
    m = min(m, x)

print(m)

Measured memory_bytes: 9016
# きりみんちゃんの配信をみてたので期待値は分かる
# 素直にTLEくらったので累積和で加減する
# え これでもだめなの
# あほだった sumしてるし
# 単純にみたら 0.5ずつ増えてるのでそうするか
# 1WA...
# N = 1の場合か？


n, k = map(int, input().split())
arr = list(map(int, input().split()))
table = {}
ans = 0
for i in range(1, 1000 + 1):
    table[i] = (i + 1) * 0.5
if n == 1:
    print(table[arr[0]])
    exit()
lis = [0 for _ in range(n)]
lis[0] = table[arr[0]]
for i in range(n - 1):
    if i + 1 < k:
        lis[i + 1] = lis[i] + table[arr[i + 1]]
    else:
        lis[i + 1] = lis[i] + table[arr[i + 1]] - table[arr[i - k + 1]]
    ans = max(ans, lis[i + 1])
print(ans)


Measured memory_bytes: 24804
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {  
  return b != 0 ? gcd(b, a % b) : a;
}//MAX
int lcm(int a, int b) { 
   return a * b / gcd(a, b);
   }
//MIN
 main() {
int n;
cin >> n;
vector<int> a(n);
int ans =0;
for(int i=0;i<n;i++){
  cin >> a.at(i);
}
for(int i=0;i<n;i++){
  for(int j=0;j<n;j++){
    if(i!=j){
     ans+=a.at(i)*a.at(j);
    }
  }
}
ans/=2;
cout << ans <<endl;
 }




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){

	int N;
	double R=0;
	cin >> N;
	vector<double> A(N);
	for (int i=0; i<N; i++){
		cin >> A.at(i);
	}
	
	for (int i=0; i<N; i++){
		R += 1/A.at(i);
	}
	
	 cout << 1/R << endl;
}	

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],b[n],c[n-1],i,pnts=0,ind,f=0;
    for(i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(i=0; i<n; i++)
    {
        cin>>b[i];
    }
    for(i=0; i<n-1; i++)
        cin>>c[i];

    for(i=0; i<n; i++)
    {
        ind=a[i]-1;
        if(a[i]!=1 && a[i]==f+1)
        {
            pnts=pnts+c[ind-1];
        }
        pnts=pnts+b[ind];
        f=a[i];
    }
    cout<<pnts<<endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

unsigned char D[252004];
bool E[252004];
int Q[252004];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();
	int n = N + 2;
	rep1(i, N) {
		int ij = n * i + 1;
		unsigned char kari = min(i - 1, N - i);
		unsigned char kari2 = 3;

		rep(j, kari) {
			D[ij++] = kari2++;
		}
		rep(j, N - kari - kari) {
			D[ij++] = kari + 3;
		}
		rep(j, kari) {
			D[ij++] = --kari2;
		}
	}

	int kotae = 0;
	rep(k, N * N) {
		int ij = getint();
		ij += (ij - 1) / N * 2 + N + 2;

		kotae += D[ij];
		E[ij] = 1;

		int p = 0, q = 0;
		Q[p++] = ij;

		while (p > q) {
			int ij = Q[q++];
			int d =	D[ij] - E[ij] + 1;

			if (D[ij - n] > d) {
				D[ij - n] = d;
				Q[p++] = ij - n;
			}
			if (D[ij + n] > d) {
				D[ij + n] = d;
				Q[p++] = ij + n;
			}
			if (D[ij - 1] > d) {
				D[ij - 1] = d;
				Q[p++] = ij - 1;
			}
			if (D[ij + 1] > d) {
				D[ij + 1] = d;
				Q[p++] = ij + 1;
			}
		}
	}

	printf("%d\n", kotae - 3 * N * N);



	Would you please return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    
    ll x, k, d;
    cin >> x >> k >> d;
    
    x = x > 0 ? x : -x;

    ll temp = min(k, x / d);
    k -= temp;
    x -= temp * d;
    if (k > 0 && k % 2 == 1) {
        x -= d;
    }

    cout << abs(x);

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
const int MOD = 1000000007;
const int INF = 10100000000000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

int a[110000];
signed main() {
  int n,k,q;cin>>n>>k>>q;
  rep(i,q){
    int aa;cin>>aa;aa--;a[aa]++;
  }
  rep(i,n){
    cout << (k-(q-a[i]) > 0 ? "Yes" : "No") << endl;
  }
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
using  P=pair<ll,ll>;
int main(){
  ll N,M,dp[100020];
  cin>>N>>M;
  unordered_map<ll,ll> mp;
  for(ll i=0;i<M;i++){
    ll a;
    cin>>a;
    mp[a]=-1;
  }
  dp[0]=1;
  for(ll i=1;i<=N;i++){
    if(mp[i]!=-1){dp[i]=(dp[i-1]+dp[i-2])%MOD;}
    else{dp[i]=0;}
  }
  cout<<dp[N]%MOD<<endl;
}

Measured memory_bytes: 5156
#include <cstdio>

int A[100 + 10], N;
int count;

void selectionSort(int A[], int N);
void swap(int& a, int& b);
void trace(int A[], int N);

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

  selectionSort(A, N);

  trace(A, N);
  printf("%d\n", count);

  return 0;
}

void selectionSort(int A[], int N) {
  for (int i = 0; i < N; ++i) {
    int minj = i;
    bool flag = false;
    for (int j = i; j < N; ++j) {
      if (A[j] < A[minj]) { minj = j; flag = true; }
    }

    if (flag) { swap(A[i], A[minj]); }
  }
}

void swap(int& a, int& b) {
  int temp = a;
  a = b;
  b = temp;

  count++;
}

void trace(int A[], int N) {
  for (int i = 0; i < N; ++i) {
    if (i) { printf(" "); }
    printf("%d", A[i]);
  }
  printf("\n");
}

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

int datanum[200000];

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

  int maxnum = -2000000000;
  int minnum = datanum[0];

  for(int j = 1; j < n ; j++) {
    maxnum = max(maxnum, datanum[j] - minnum);
    minnum = min(minnum, datanum[j]);
  }

  cout << maxnum << endl;

}


Measured memory_bytes: 3852
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#define MAX 1000
#define DIAGONAL 1
#define TOP 0

using namespace std;

struct Item{ int value, weight; };

int N, W;
Item items[MAX];
int C[MAX+1][MAX+1];

int knapsack(){
    for ( int w = 0; w <= W; w++ ) C[0][w] = 0;
    for ( int i = 1; i <= N; i++ ) C[i][0] = 0;
    for ( int i = 1; i <= N; i++ ){
	for ( int w = 1; w <= W; w++ ){
	    C[i][w] = C[i-1][w];
	    for ( int j = 1; j*items[i].weight <= w; j++ ){
		if ( j*items[i].value + C[i-1][w - j*items[i].weight] > C[i][w] ){
		    C[i][w] = j*items[i].value + C[i-1][w - j*items[i].weight];
		}
	    }
	}
    }
    return C[N][W];
}

int main(){
    int C[MAX], V[MAX], D[MAX], L[MAX];
    string line;
    while(cin >> N >> W){
	int maxv = 0;
	for ( int i = 0; i < N; i++ ){
	    getline(cin, line);
	    getline(cin, line);
	    cin >> C[i] >>  V[i] >> D[i] >> L[i];
	}
	for ( int i = 0; i < N; i++ )  items[i+1].weight = C[i];

	for ( int i = 0; i < N; i++ )  items[i+1].value = V[i];
	maxv = max(maxv, knapsack());
	for ( int i = 0; i < N; i++ )  items[i+1].value = D[i];
	maxv = max(maxv, knapsack());
	for ( int i = 0; i < N; i++ )  items[i+1].value = L[i];
	maxv = max(maxv, knapsack());


	cout << maxv << endl;
    }
    return 0;
}

Measured memory_bytes: 2408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0120
{
    public class Program

    {
        public static void Main(string[] args)
        {
            while (true)
            {

                string line = Console.ReadLine();
                if (string.IsNullOrEmpty(line)) return;

                int[] items = Array.ConvertAll(line.Trim().Split(' '), e => int.Parse(e));
                int w = items[0];
                int[] r = items.Skip(1).ToArray();

                int n = r.Length;
                double[,] dp = new double[(1 << n), n];
                for (int i = 0 ; i < dp.GetLength(0) ; i++)
                {
                    for (int j = 0 ; j < dp.GetLength(1) ; j++)
                    {
                        dp[i, j] = int.MaxValue;
                    }
                }

                for (int i = 0 ; i < dp.GetLength(0) ; i++)
                {
                    for (int j = 0 ; j < n ; j++)
                    {
                        if (i == 0)
                        {
                            dp[(1 << j), j] = Math.Min(dp[(1 << j), j], r[j]);
                        }
                        else
                        {
                            for (int k = 0 ; k < dp.GetLength(1) ; k++)
                            {
                                if (dp[i, k] == int.MaxValue) continue;

                                int next = i | (1 << j);
                                dp[next, j] = Math.Min(dp[next, j], dp[i, k] + getDistance(r[k], r[j]));
                            }
                        }
                    }
                }

                double ans = double.MaxValue;
                for (int i = 0 ; i < n ; i++) ans = Math.Min(ans, dp[(1 << n) - 1, i] + r[i]);
                Console.WriteLine(ans - 1e-8 <= w ? "OK" : "NA");
            }
        }

        public static double getDistance(double r1, double r2)
        {
            return 2 * Math.Sqrt(r1 * r2);
        }


        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RStAr(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }

}



Measured memory_bytes: 21024
n = input()
result = ""
for x in xrange(1,n+1):
    if x % 3 == 0:
        result = result + " " + str(x)

    elif x % 10 == 3:
        result = result + " " + str(x)

    else :
        i = x
        while i :
            i /= 10
            if i % 10 == 3:
                result = result + " " + str(x)
                break
print result

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

long long h, w;
vector<string> s;

long long solve();
long long calc(int l, int r);

int main() {
  cin >> h >> w;
  s.resize(h);
  for (auto &p : s) cin >> p;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  calc(1, 2);
  long long res = 0;
  for (int i = 1; i < w; ++i) res += calc(i - 1, i);
  return res;
}

long long calc(int l, int r) {
  vector<vector<long long>> memo(2 * h + 1, vector<long long>(h + 1, 0));
  for (int i = -h; i <= h; ++i)
    for (int j = 0; j < h; ++j) {
      memo[i + h][j + 1] = memo[i + h][j];
      if (0 <= i + j && i + j < h) memo[i + h][j + 1] += s[i + j][l] == s[j][r];
    }
  vector<vector<long long>> dp(h + 1,
                               vector<long long>(h + 1, (long long)(1e16)));
  dp[h][h] = 0;
  for (int i = h; i >= 0; --i)
    for (int j = h; j >= 0; --j)
      if (i || j) {
        int cost = memo[j - i + h][i];
        if (i) dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + cost);
        if (j) dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + cost);
      }
  return dp[0][0];
}

Measured memory_bytes: 5580
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = (int) 1e5;

int p[MAXN + 1];

int main() {
    //fstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++)
        cin >> p[i];
    int ans = 0;
    for(i = 1; i < n; i++) {
        if(p[i] == i) {
            swap(p[i], p[i + 1]);
            ans++;
        }
    }
    if(p[n] == n) {
        swap(p[n - 1], p[n]);
        ans++;
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 640
use std::collections::HashSet;
fn main() {
    let v = read_vec::<u32>()
        .into_iter()
        .collect::<HashSet<_>>()
        .iter()
        .count();
    println!("{}", v);
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352