akhauriyash/Code-Regression huggingface dataset:
# dp[i]
# ある石が初めて出てくるときは、場合の数は増えない
# 1 2  -> ここまでは1通り
# 1 2 3 -> 3が初めて出てきたので、1通りのまま
# 1 2 3 2 -> 2は二度目に出てきたので1,2,3までの場合の数1と、2が最後に出た場合の数1を足す
# dpは[1,1,1,2]となる
# 1 2 3 2 2 -> 前回と同じ文字が出てきたときはパターンが増えない（そこで切れない）
# dpは[1,1,1,2,2]
# 1 2 3 2 2 3 -> 3は二度目に出てきたので、1,2,3,2,2までの場合の数2と、3が最後に出た場合の数1を足す
# dpは[1,1,1,2,2,3]
# dpの他に、「ある数が最後に出てきたときのindex」を管理する

N = int(input())
C = [None] * N
for i in range(N):
  C[i] = int(input())

DIV = 10 ** 9 + 7

dp = [0 for i in range(N)]
dp[0] = 1
index = [-1] * (max(C)+1) # ある数が最後に出てきたindex
index[C[0]] = 0 # ループを1から回すので、最初の数だけ「最後に登場したindexは0」を代入

for i in range(1,len(C)):
  if C[i] == C[i-1]:
    dp[i] = dp[i-1] # 直前と同じ文字のときはパターンが増えない
  elif index[C[i]] == -1:
    # 初めて出てきた文字のときは場合の数が増えない
    dp[i] = dp[i-1]
  else:
    # 二回目以降に出てきた場合、場合の数を足す
    dp[i] = ( dp[i-1] + dp[index[C[i]]] ) % DIV
  # 最後に出てきたindexを更新する
  index[C[i]] = i

print(dp[-1])

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e10;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
//ifstream myfile("C:\\Users\\riku\\Downloads\\01.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;


int main() {
    string s, t;

    cin >> s >> t;

    vector<char> q(26, 27);
    vector<char> r(26, 27);

    for (int i = 0; i < s.size(); i++) {
        char sc = s[i] - 'a';
        char tc = t[i] - 'a';



        if (q[sc] == 27) {
            q[sc] = tc;
        } else {
            if (tc != q[sc]) {
                cout << "No" << endl;
                return 0;
            }
        }


        if (r[tc] == 27) {
            r[tc] = sc;
        } else {
            if (sc != r[tc]) {
                cout << "No" << endl;
                return 0;
            }
        }
    }


    cout << "Yes" << endl;
}


Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int H,N;
    cin >> H >> N;
    vector<int> A(N);
    int sum = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int i = 0; i < N; i++){
        sum += A[i];
    }
    if(sum >= H){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl; 
    }

}

Measured memory_bytes: 640
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int mod = 10000007;
const int inf = 1001001001;



int main(void) {
  int n,k;
  string s;
  cin >> n >> k >> s;
  if(s[k-1] == 'A')s[k-1] = 'a';
  else if(s[k-1] == 'B')s[k-1] = 'b';
  else s[k-1] = 'c';
  cout << s << endl;
}


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

const int MAXN = 1010;

struct Edge
{
	int to, nxt;
}e[MAXN << 1];
int tot, h[MAXN];

inline void add(int u, int v)
{
	e[++tot] = (Edge){v, h[u]};
	h[u] = tot;
}

int n, m, d[MAXN], f[MAXN];
int cnt, num, ans[MAXN], now[MAXN];

void solve(int s)
{
	memset(d, 0, sizeof(d));
	memset(f, 0, sizeof(f));
	queue<int> q; q.push(s);
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		for(int i = h[x]; i; i = e[i].nxt)
		{
			int y = e[i].to;
			if(!d[y])
			{
				f[y] = x;
				d[y] = 1;
				q.push(y);
			}
		}
		if(d[s]) break;
	}
	if(!d[s]) {num = MAXN; return;}
	now[num = 1] = s;
	int p = f[s];
	while(p && p != s)
	{
		now[++num] = p;
		p = f[p];
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		add(u, v);
	}
	cnt = MAXN;
	for(int i = 1; i <= n; ++i)
	{
		solve(i);
		if(num < cnt)
		{
			cnt = num;
			for(int i = 1; i <= cnt; ++i) ans[i] = now[i];
		}
	}
	if(cnt == MAXN) puts("-1");
	else
	{
		printf("%d\n", cnt);
		for(int i = 1; i <= cnt; ++i) printf("%d\n", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pi acose(-1)
#define rep(i,x) for(int i=0; i<(x); i++)
typedef long long ll;
using namespace std;

int main()
{
    char s1[200001], s2[200001];
    int ln, i, cnt=0;
    cin>>s1>>s2;
    ln = strlen(s1);

    rep(i,ln){
        s1[i]= tolower(s1[i]);
        s2[i]= tolower(s2[i]);
    }
    rep(i,ln){
        if(s1[i]!=s2[i]){
            cnt++;
        }
    }
    printf("%d\n", cnt);

    return 0;
}


Measured memory_bytes: 4084
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n;
vector<pair<int,string> > a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    string x;
    int sum=0;
    bool c=false;
    for (int i = 0; i < n; i++)
    {
        int temp;
        string temps;
        cin >>temps >>temp;
        a.push_back(make_pair(temp,temps));
    }
    cin>>x;
    for(int i=0;i<n;i++){
        if(a[i].second==x){
            c=true;
        }
        else if(!c){
            
        }
        else{
            sum+=a[i].first;
        }
    }
    cout << sum << "\n";
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;

const int N=370;
const int M=30;

int D,ans,T,d,q,start;
int s[N][M],lst[M],c[M],t[N];

bool time_out(){
	return clock()-start>950;
}

int calc(){
	int sum=0;
	for (int i=1;i<=26;i++) lst[i]=0;
	for (int i=1;i<=D;i++){
		sum+=s[i][t[i]];
		lst[t[i]]=i;
		for (int j=1;j<=26;j++) sum-=c[j]*(i-lst[j]);
	}
	return sum;
}

int main(){
	scanf("%d",&D);
	for (int i=1;i<=26;i++) scanf("%d",&c[i]);
	for (int i=1;i<=D;i++)
		for (int j=1;j<=26;j++) scanf("%d",&s[i][j]);
	srand(time(0));
	start=clock();
	for (int i=1;i<=D;i++) t[i]=1;
	ans=calc();
	while (!time_out()){
		int sum,tmp;
		d=rand()%D+1; q=rand()%26+1;
		tmp=t[d];
		t[d]=q; sum=calc();
		if (sum>ans) ans=sum;
		else t[d]=tmp;
	}
	for (int i=1;i<=D;i++) printf("%d\n",t[i]);
	return 0;
}

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

using namespace std;

int main()
{
string s; cin >> s;

for(int i = 0; i < s.size(); ++i)
{
//i == 0, s[0] is first
if(i % 2)//if i is even, do process from first literal
{
if(s[i] == 'R')
{
std::cout << "No";
return 0;
}
}
else
{
if(s[i] == 'L')
{
cout << "No";
return 0;
}
}
}

cout << "Yes";
}


Measured memory_bytes: 256
//#include "pch.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int a, b;
	vector<bool>flag(3, false);

	cin >> a >> b;
	a--; b--;
	flag[a] = true;
	flag[b] = true;

	for (int i = 0; i < 3; i++) {
		if (flag[i] == false) {
			cout << i + 1 << endl;
				break;
		}
	}





	return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
s = [list(map(int,input().split()))for i in range(m)]
p = list(map(int,input().split()))
ans = 0
def check(x):
    ok = True
    for i in range(m):
        cnt = 0
        for j in range(len(s[i])):
            if not j:continue
            if (x>> (s[i][j]-1))%2:cnt +=1
        if cnt%2 != p[i]:
            ok = False
            break
    return ok
for i  in range(2**n):
    if check(i):ans +=1
print(ans)
    

Measured memory_bytes: 40816
from collections import deque
n,m = map(int,input().split())

tree = [[] for i in range(n)]
for i in range(m):
  tmp_a,tmp_b = map(int,input().split())
  tree[tmp_a-1].append(tmp_b-1)
  tree[tmp_b-1].append(tmp_a-1)
def bfs():
  q = deque()
  visited =[False]*n
  visited[0]=True
  for elem in tree[0]:
    q.append([elem,1])
  while q:
    i,cnt = q.popleft()
    if i == n-1 and cnt <=2 :
      print("POSSIBLE")
      exit()
    if not visited[i]:
      visited[i] = True
      if cnt<=1:
        for elem in tree[i]:
          q.append([elem,cnt+1])

bfs()
print("IMPOSSIBLE")
      

Measured memory_bytes: 49868
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define mp make_pair
#define pb push_back
#define pf push_front
#define ss second
#define ff first
#define sz(x) (int)x.size()
#define newl "\n"
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define vl vector<ll>
#define pll pair<ll, ll>
#define vll vector<pll>
#define coutp cout << fixed << setprecision(12)
#define mem(x, val) memset(x, val, sizeof(x))
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define all(v) (v).begin(), (v).end()

const ld pi = 3.14159265359;
ll INF = 1e18 + 10;
ll MOD = 998244353;
ll mod = 1e9 + 7;

inline ll add(ll a, ll b, ll m)
{
    if ((a + b) >= m)
        return (a + b) % m;
    return a + b;
}

inline ll mul(ll a, ll b, ll m)
{
    if ((a * b) < m)
        return a * b;
    return (a * b) % m;
}

ll power(ll x, ll y, ll m)
{
    ll res = 1;
    x = x % m;
    if (x == 0)
        return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % m;
        y = y >> 1;
        x = (x * x) % m;
    }
    return res;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<string> v(n);
    vector<vl> dp(n,vl(m,0));
    for(int i=0;i<n;i++) {
        cin>>v[i];
    }
    dp[0][0]=1;
    for(int i=1;i<m;i++) {
        if(v[0][i]=='#') dp[0][i]=0;
        else
            dp[0][i] = dp[0][i-1]; 
    }
    for (int i=1;i<n;i++) {
        if (v[i][0]=='#') dp[i][0]=0;
        else
            dp[i][0] = dp[i-1][0];
    }


    for(int i=1;i<n;i++) {
        for(int j=1;j<m;j++) {
            if(v[i][j]=='#') dp[i][j]=0;
            else 
                dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
        }
    }

    cout<<dp[n-1][m-1];

}

int main()
{
    fastio;
    int t;
    t = 1;
    //cin >> t;
    //int test=t;
    
    while (t-- > 0)
    {
        //cout<<"Case #"<<(test-t)<<": ";
        solve();
        cout << newl;
    }

    return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << (A * B) / gcd(A, B) << endl;
}

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

int main(){
  ll n;
  cin >> n;
  
  vector<ll>sum(5000);
  rep(i,5000){
    sum[i]=(i)*(i+1)/2;
  }
  ll left = lower_bound(sum.begin(),sum.end(),n)-sum.begin();
  vector<ll>vec;
  vec.push_back(left);
  
  ll ans = left;
  ll k = left-1;
  while(ans<n){
    ans += k;
    if(ans>n){
      ans -= k;
      k--;
    }
    else{
      vec.push_back(k);
      k--;
    }
  }
  
  ll m = vec.size();
  rep(i,m){
    cout << vec[i] << endl;
  }
  return 0;
  
}

Measured memory_bytes: 384
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  int i,h[100010],sum=0,ans=0;
  int n;
  cin >> n;
  for(i=0;i<n;i++){
    cin >> h[i];
  }
  for(i=1;i<n;i++){
    if(h[i-1]>=h[i]){
      sum++;
    }
    else{
      ans=max(ans,sum);
      sum=0;
    }
  }
  ans=max(ans,sum);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4016
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <string>
using namespace std;

int main() {
	int s, w;
	string str;

	cin >> s >> w;

	str = s < w ? "unsafe" : "safe";
	if (s == w) {
		str = "unsafe";
	}

	cout << str;
	
	return 0;
}


Measured memory_bytes: 3624
from decimal import *
sum = 0
cnt = 0
nums = 0
while 1:
    try:
        price, num = (int(x) for x in input().split(','))
        sum += price * num
        cnt += 1
        nums += num
    except EOFError:
        break

print(sum)
nums = Decimal(nums / cnt).quantize(Decimal('0'), rounding=ROUND_HALF_UP)
print(nums)


Measured memory_bytes: 6408
from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def yes(n): print("Yes") if n else print("No")
def debug(*x, sep=" ", end="\n"):
    for item in x:
        stderr.write(repr(item))
        stderr.write(sep)
    stderr.write(end)

r = int(input())
if r < 1200:
    print("ABC")
elif r < 2800:
    print("ARC")
else:
    print("AGC")

Measured memory_bytes: 4196
S = list(input())
T = list(input())

sl = len(S)
tl = len(T)

for i in range(sl-tl,-1,-1):
    flag = True
    for j in range(tl):
        s = S[i+j]
        t = T[j]
        if (s != '?')and(s != t):
            flag = False
            break
    if flag == True:
        for j in range(tl):
            S[i+j] = T[j]
        for k in range(sl):
            if S[k] == '?':
                S[k] = 'a'
        print("".join(S))
        exit()

print("UNRESTORABLE")

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<math.h>
#include<tuple>
#include<string.h>
#include <numeric> 
#include<unordered_map>
using namespace std; 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define pp(...) "\033[94m [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]\033[0m"
#define pp1(...) "\033[1;47;35m" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]\033[0m"
#define dg(x) debug() << pp1(x)
#define dg1(x) debug() << pp(x)
#define dg2(x,y) debug() << pp(x) pp(y)
#define dg3(x,y,z) debug() << pp(x) pp(y) pp(z)
#define dg4(w,x,y,z) debug() << pp(w) pp(x) pp(y) pp(z)
#define int long long
#define all(x) x.begin() , x.end()
#define clr(x) memset(x , 0 , sizeof x);
#define sz(x) (int)x.size()
template<typename T> void db(T x ){ debug() <<">>> " <<  x; }
template<typename T> void db(T x , T y){ debug() <<">>> " <<  x <<" , "<< y; }
template<typename T> void db(T x , T y , T z){ debug() <<">>> "<< x <<" , "<< y <<" , "<< z; }
template<typename T> void db(T x , T y , T z , T a){ debug() <<">>> "<< x <<" , " << y <<" , "<< z <<" , "<< a; }
const int xx = 2e5;
const int Mod = 1e9 + 7;
const int inf = 1e18;
const int Maxn = 20010;
auto in = [](auto &&... args) { (cin >> ... >> args); };


signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n , k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int>inversion(n) , Cnt(n);

  for(int i = 0; i < n ; i++) {
    int c = 0;
    for(int j = i + 1; j < n; j++) {
      if(a[j] < a[i]) c++;
    }
    inversion[i] = c;

    c = 0;
    for(int j = 0; j < n; j++) {
      if(i == j) continue;
      if(a[j] < a[i]) c++;
    }
    Cnt[i] = c;
  }
  dg(inversion);dg(Cnt);
  int ans = 0;
  int K = (k * (k - 1) / 2);
  K = K % Mod;
  for(int i = 0; i < n; i++) {
    int x = (inversion[i] * k) % Mod;
    int y = ( K * Cnt[i]) % Mod;
    ans += (x + y) % Mod;
    ans = ans % Mod; 
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <math.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define repP(i, a, b) for(int i = a; i < b; i++)
#define repM(i, a, b) for(int i = a - 1; i >= b; i--)

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0, i = 0, j = 0;
  int num = 0, count = 0, ans = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int a1[256], a2[512], a3[1024];
  //char s1[200000], s2[200000], s3[200000];
  //string s1, s2, s3;
  
  cin >> a;
  
  if(a % 2 == 0){
    cout << a / 2 - 1;
  }else{
 	 cout << a / 2 << endl;
  }
}

Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector.Unboxed as VU

main :: IO ()
main = do
  k <- unsafeTextToInt <$> T.getLine :: IO Int
  print . fromLunlunToInt $ k

ls :: VU.Vector (Int, Int)
ls = VU.constructN (succ $ 10 ^ 5) rec
  where
    rec v | k < 10    = (0, k)
          | r <= min 8 r' = (k', succ r)
          | otherwise = (k'', max 0 (pred r''))
      where
        k = VU.length v
        (k', r) = VU.last v
        r' = snd $ v VU.! k'
        k'' = succ k'
        r'' = snd $ v VU.! k''

fromLunlunToInt :: Int -> Int
fromLunlunToInt 0 = 0
fromLunlunToInt k = 10 * fromLunlunToInt k' + r
  where
    (k', r) = ls VU.! k

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 2556
#include <bits/stdc++.h> 
 
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<long, long> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
const double EPS=1e-10;
 
typedef int Weight;
//typedef
//------------------------------------------
 
typedef int Weight;
//typedef
//------------------------------------------
 
 
int main(){
    int N;cin>>N;
    long c=0;
    int tmp=1;
    while(1){
        if(tmp*(tmp-1)==2*N){
            c=tmp;break;
        }else if(tmp*(tmp-1)>2*N){
            break;
        }
        tmp++;
    }
    vector<long>used(N);
    if(c==0){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
        cout<<c<<endl;
        vector<vector<int>>res(c);
        int cnt=1;
        while(cnt<=N){
            REP(i,c){
                FOR(j,i+1,c){
                    res[i].PB(cnt);
                    res[j].PB(cnt);
                    cnt++;
                }
            }
        }
        REP(i,c){
            cout<<SZ(res[i]);
            for(auto r:res[i]){
                cout<<" "<<r;
            }
            cout<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3072
//#define DEBUGGING  // Enables DEBUG macro.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

#ifndef DEBUGGING
#define DEBUG(...)
#else
template <typename T>
void _debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void _debug(T value, Ts... args) {
  std::cerr << value << ", ";
  _debug(args...);
}
#define DEBUG(...)                     \
  do {                                 \
    cerr << " (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ": ";      \
    _debug(__VA_ARGS__);               \
    cerr << endl;                      \
  } while (0)
#endif

const int L = 100'001;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M;
  cin >> N >> M;
  vector<int> X(N);
  for (auto& x : X) cin >> x;

  vector<int> counter(L);
  for (auto x : X) {
    ++counter[x];
  }

  vector<int> pair_cnt(M), rem_cnt(M);
  REP(x, L) {
    int cx = counter[x];
    pair_cnt[x % M] += (cx / 2) * 2;
    rem_cnt[x % M] += cx % 2;
  }

  i64 ans = 0;
  for (int i = 1; i <= M / 2; ++i) {
    int j = M - i;
    if (i >= j) break;
    int mr = min(rem_cnt[i], rem_cnt[j]);
    ans += mr;
    DEBUG(i, j, rem_cnt[i], rem_cnt[j], mr, ans);
    rem_cnt[i] -= mr;
    rem_cnt[j] -= mr;
    if (rem_cnt[i] > 0) {
      mr = min(rem_cnt[i], pair_cnt[j]);
      ans += mr;
      DEBUG(i, j, rem_cnt[i], pair_cnt[j], mr, ans);
      rem_cnt[i] -= mr;
      pair_cnt[j] -= mr;
    }
    if (rem_cnt[j] > 0) {
      mr = min(rem_cnt[j], pair_cnt[i]);
      ans += mr;
      DEBUG(i, j, pair_cnt[i], rem_cnt[j], mr, ans);
      rem_cnt[j] -= mr;
      pair_cnt[i] -= mr;
    }
    ans += pair_cnt[i] / 2;
    ans += pair_cnt[j] / 2;
    pair_cnt[i] %= 2;
    pair_cnt[j] %= 2;
  }
  ans += rem_cnt[0] / 2 + pair_cnt[0] / 2;
  if (M % 2 == 0) {
    int k = M / 2;
    ans += rem_cnt[k] / 2 + pair_cnt[k] / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

class Zp {
	const int p = 1000000007;
	ll r;
	void set(ll x) {
		while (x < 0) x += p;
		r = x % p;
	}

public:
	Zp(ll x) { set(x); }
	Zp() { set(0); }

	Zp operator-() const { return Zp(-r); }
	Zp &operator=(ll y) {
		set(y);
		return *this;
	}
	Zp &operator=(const Zp &y) { return *this = y.r; }

	Zp &operator+=(ll y) {
		set(r + y);
		return *this;
	}
	Zp &operator-=(ll y) { return *this += -y; }
	Zp &operator*=(ll y) {
		set(r * y);
		return *this;
	}
	Zp &operator/=(ll y) { return *this *= inv(y); }
	Zp operator+(ll y) const { return Zp(r + y); }
	Zp operator-(ll y) const { return *this + (-y); }
	Zp operator*(ll y) const { return Zp(r * y); }
	Zp operator/(ll y) const { return *this * inv(y); }

	Zp &operator+=(const Zp &y) { return *this += y.r; }
	Zp &operator-=(const Zp &y) { return *this -= y.r; }
	Zp &operator*=(const Zp &y) { return *this *= y.r; }
	Zp &operator/=(const Zp &y) { return *this /= y.r; }
	Zp operator+(const Zp &y) const { return *this + y.r; }
	Zp operator-(const Zp &y) const { return *this - y.r; }
	Zp operator*(const Zp &y) const { return *this * y.r; }
	Zp operator/(const Zp &y) const { return *this / y.r; }

	Zp pow(int n) const {
		if (n == 0) return 1;
		if (n % 2) return *this * pow(n - 1);
		Zp tmp = pow(n / 2);
		return tmp * tmp;
	}
	Zp inv(int x) const { return Zp(x).pow(p - 2); }
	Zp inv() const { return inv(r); }

	ll get() const { return r; }

	friend istream &operator>>(istream &istr, Zp &x) {
		istr >> x.r;
		x.set(x.r);
		return istr;
	}
	friend ostream &operator<<(ostream &ostr, const Zp &x) {
		ostr << x.r;
		return ostr;
	}
};
class Comb {
	vector<Zp> fact, ifact;

public:
	Comb(int N) : fact(N + 1), ifact(N + 1) {
		fact[0] = 1;
		REP(i, N)
		fact[i + 1] = fact[i] * (i + 1);
		ifact[N] = fact[N].inv();
		REPR(i, N)
		ifact[i] = ifact[i + 1] * (i + 1);
	}
	Zp operator()(int n, int k) const {
		return fact[n] * ifact[n - k] * ifact[k];
	}
	Zp f(int k) const { return fact[k]; }
	Zp invf(int k) const { return ifact[k]; }
};

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

	int K;
	string S;
	cin >> K >> S;
	int N = SZ(S);
	Zp res = 0;
	Comb comb(N + K);
	FOR(right, N, N + K + 1) {
		res += Zp(25).pow(right - N) * Zp(26).pow(N + K - right) * comb(right - 1, N - 1);
	}
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 66828
N = int(input())
p = list(map(int, input().split()))

p_ = sorted(p)

number_of_different = 0
answer = 'YES'
for pi, pi_ in zip(p, p_):
    if pi is not pi_:
        number_of_different += 1

    if number_of_different >= 3:
        answer = 'NO'
        break

print(answer)


Measured memory_bytes: 2940
#include<stdio.h>

int main (){
	int num;
	int stay[100];
	int hp[100];
	int point, minlhp;
	scanf("%d", &num);

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

//開催地ごとの消費体力を計算
	point = 0;
	minlhp = 1000000000;
	for(int i=1; i<100; i++){
		//iで行うときの各人の消費体力をhp[i]に格納
		hp[i]=0;
		for(int j=0; j<num; j++){
			hp[i] += (stay[j] - i)*(stay[j] - i);
		}
		if(hp[i] < minlhp){
			minlhp = hp[i];
			point = i;
		}
	}

	printf("%d\n", minlhp);

	return 0;
}


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

int main(){
    long long int N;

    //入力
    cin >> N;
    long long int ans=0;
    for(long long int i=1;i<N;i++){
        for(long long int j=1;N-i*j>=1;j++){
            ans += 1;
        }
    }
        cout << ans << endl;
}

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

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

  int ave = round(accumulate(v.begin(), v.end(), 0.0) / n);
  int sum = 0;
  for (int x : v) {
    sum += pow(x - ave, 2);
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
using namespace std;
int main()
{
    int a,i;
    map<int,int>b;
    for(i=0;i<3;i++){
        cin>>a;
        b[a]++;
    }
    if(b[5]==2&&b[7]==1)
        puts("YES");
    else
        puts("NO");
}


Measured memory_bytes: 3632
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<double,P> PP;
struct edge { int to; int cost; };
int imos[100006];
signed main() {
	int n, m; cin >> n >> m;
	rep(i, m) {
	
		int l, r; cin >> l >> r;
		imos[l]++;
		imos[r + 1]--;
	}
	rep(i, 100003)imos[i + 1] += imos[i];
	int cnt = 0;
	rep(i, 100003) {
		if (imos[i] == m)cnt++;
	}cout << cnt << endl;
}

Measured memory_bytes: 1024
#定数
#1≦n≦2*10^5
n = int(input())

#先頭と末尾の数の組み合わせの個数を格納するリストを作成
HT = [[0 for i in range(10)] for j in range(10)] #Head Tail list
for i in range(1, n+1):  #O(n)
    d = len(str(i)) #digit
    hnum = i // (10**(d-1))  #head_num
    tnum = i % 10   #tail_num
    HT[hnum][tnum] += 1

#答えの計算
ans = 0
#headとtailが等しい場合
#9通り
for i in range(1, 10):
    ans += HT[i][i] ** 2
#headとtailが等しくない場合
#36通り
for i in range(1,10):
    for j in range(i+1, 10):
        ans += (HT[i][j] * HT[j][i]) * 2

#答えを出力
print(ans)



    


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
vector<ll> H;
ll dp[MAX_N];

// 現在 i にいるときの最小コスト
ll dfs(ll i = 0) {
    if(i == N-1) { return 0; }

    ll& ret = dp[i];
    if(~ret) { return ret; }

    // 一つ前
    ret = dfs(i+1) + abs(H[i] - H[i+1]);
    // 二つ前
    if(i < N-2) { ret = min(ret, dfs(i+2) + abs(H[i] - H[i+2])); }

    return ret;
}

signed main()
{
    cin >> N;
    H.assign(N, 0);
    REP(i, N) { cin >> H[i]; }
    MINUS(dp);
    printf("%lld\n", dfs());
    return 0;
}


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

int main() {
  int N,T,A,i,nya;
  double An;
  An=100000.0;
  cin>>N>>T>>A;
  int H[N]={0};
  double O[N]={0.0};
  for(i=0;i<N;i++){
  cin>>H[i];
  }
 
  for(i=0;i<N;i++){
  O[i]=T-H[i]*0.006-A;
    if(O[i]<0){
    O[i]=O[i]*(-1);
    }
  }
  
  for(i=0;i<N;i++){
    
  if(O[i]<An){
  An=O[i];
    nya=i+1;
  }
    
  }
  cout<<nya<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#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;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline ll getint() {
	ll A = 0;
	if (ci - cn + 24 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}


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


	int N = getint();
	ll kazu[20] = {};
	const int mod = 1e9 + 7;
	const ll m = 1 + (1 << 20) + (1ll << 40);
	rep(i, N) {
		ll a = getint();
		rep(j, 20) kazu[j] += a >> j & m;
	}

	ll kotae = 0;
	const ll m2 = (1 << 20) - 1;
	rep(j, 20) {
		ll tmp = (1ll << j) % mod;
		ll tmpk = (kazu[j] & m2);
		tmpk = tmpk * (N - tmpk) % mod;
		kotae += tmp * tmpk % mod;

		tmp = (1ll << (j + 20)) % mod;
		tmpk = (kazu[j] >> 20 & m2);
		tmpk = tmpk * (N - tmpk) % mod;
		kotae += tmp * tmpk % mod;

		tmp = (1ll << (j + 40)) % mod;
		tmpk = (kazu[j] >> 40 & m2);
		tmpk = tmpk * (N - tmpk) % mod;
		kotae += tmp * tmpk % mod;
	}

	printf("%lld", kotae% mod);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template<class _T> static void getint(_T& a) {
	std::cin >> a;
}
template<class _T> static void getint(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void B();

int main()
{
	B();
	fflush(stdout);
	return 0;
}

static void B()
{
	int X, Y;
	getint(X, Y);

	bool exist = false;
	for (int i = 0; i <= X; i++) {
		if ((i * 2 + (X - i) * 4) == Y) {
			exist = true;
			break;
		}
	}
	printf("%s\n", exist ? "Yes" : "No");
}


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<numeric>

using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, w, wi,vi;
	long long w1;
	cin >> n >> w;
	vector<vector<long long>> val(4, vector<long long>());
	cin >> w1 >> vi;
	val[0].push_back(vi);
	for (int i = 1; i < n; i++) {
		cin >> wi >> vi;
		val[wi - w1].push_back(vi);
	}
	for (auto & vec : val) {
		sort(vec.rbegin(), vec.rend());
		vec.insert(vec.begin(), 0);
		for (int i = 1; i < vec.size(); i++) {
			vec[i] += vec[i - 1];
		}
	}
	long long ans{ 0 };
	for (int i = 0; i<val[0].size(); i++) {
		if (i*w1 > w) break;
		for (int j = 0; j<val[1].size(); j++) {
			if (i*w1 + j * (w1 + 1) > w)break;
			for (int k = 0;k<val[2].size(); k++) {
				if (i*w1 + j * (w1 + 1) + k * (w1 + 2) > w)break;
				for (int l = 0;l<val[3].size(); l++) {
					if (i*w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > w) break;
					ans = max(ans, val[0][i] + val[1][j] + val[2][k] + val[3][l]);
				}
			}
		}
	}
	cout << ans << endl;


	return 0;
}

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

namespace ABC145
{
    class A
    {
        static void Main(string[] args)
        {
            int r = int.Parse(Console.ReadLine());
            double s1 = 1 * 1 * Math.PI;
            double s2 = r * r * Math.PI;
            Console.WriteLine(s2 / s1);
        }
    }
}


Measured memory_bytes: 13140
// #include <bits/stdc++.h>
#include<climits>
#include<cmath>
#include<cstdio>
#include<deque>
#include<map>
#include<set>
#include<vector>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<numeric>
#include<string>
#include<tuple>
using namespace std;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define pt pop_front
#define pk pop_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}

inline void solve(void){
  long N,M;
  in(N,M);
  vector<bool>C(N+1);
  vector<int>B(N+1,1);
  C[1]=true;
  int x,y;
  rep(i,M){
    in(x,y);
    if(C[x])C[y]=true;
    B[x]--;
    B[y]++;
    if(B[x]==0)C[x]=false;
  }
  long ans=0;
  rep(i,N+2)if(C[i]&&B[i]>0)ans++;
  out(ans);
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 640
// AOJ
// Minimum Spanning Tree
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=ja
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int V, E; cin >> V >> E;
    vector< vector<pair<int, int>> > g(V);
    for (int i = 0; i < E; i++) {
        int s, t, w; cin >> s >> t >> w;
        g[s].push_back(make_pair(w, t));
        g[t].push_back(make_pair(w, s));
    }

    int total_weight = 0;
    vector<bool> done(V, false);
    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>
    > q;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        pair<int, int> e = q.top(); q.pop();
        int& w = e.first, v = e.second;
        if (done[v]) continue;
        total_weight += w;
        done[v] = true;
        for (const auto& f : g[v]) {
            if (!done[f.second])
                q.push(f);
        }
    }
    cout << total_weight << endl;
}



Measured memory_bytes: 6808
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
typedef long double lb;
#define ri register int
const lb PI=3.141592653589793238462643383279;
const ll inf=1000000000000000000ll;
const int N=1000005,M=998244353;
long long qpow(long long a,long long b)
{
	long long s=a,ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*s%M;
		b>>=1;
		s=s*s%M;
	}
	return ans;
}
int n,i,l,r,j,dp[1005];
char ans[1005][1005];
string a[7]={"aabbc..",
			"bbaac..",
			"aabb.dd",
			"....aba",
			"....aba",
			"....bab",
			"....bab"};
string b[4]={	"aabc",
				"ddbc",
				"fgee",
				"fghh"};
string c[5]={	"aa.bc",
				".ddbc",
				"eefgg",
				"h.f.i",
				"h.kki"};
int main()
{
	scanf("%d",&n);
	if(n<=2)
	{
		puts("-1");
		return 0;
	}
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			ans[i][j]='.';
	dp[0]=dp[4]=dp[5]=dp[7]=1;
	if(n%3==0)
		for(i=1;i<=n;i+=3)
			ans[i][i]=ans[i][i+1]=ans[i+1][i+2]=ans[i+2][i+2]='a';
	else
	{
		l=1;
		int tn=n;
		while(n)
		{
			if(n-4>=7||dp[n-4])
			{
				n-=4;
				for(i=0;i<4;++i)
					for(j=0;j<4;++j)
						ans[i+l][j+l]=b[i][j];
				l+=4;
				continue;
			}
			if(n-5>=7||dp[n-5])
			{
				n-=5;
				for(i=0;i<5;++i)
					for(j=0;j<5;++j)
						ans[i+l][j+l]=c[i][j];
				l+=5;
				continue;
			}
			if(n-7>=7||dp[n-7])
			{
				n-=7;
				for(i=0;i<7;++i)
					for(j=0;j<7;++j)
						ans[i+l][j+l]=a[i][j];
				l+=7;
			}
		}
		n=tn;
	}
	for(i=1;i<=n;++i)
		printf("%s\n",ans[i]+1);
}


Measured memory_bytes: 2176
#include <stdio.h>
#define MAX 101

int n;

int main(){
    int x,i,j,u,k,G[MAX][MAX];
    
    for(i=0;i<MAX;i++){
        for(j=0;j<MAX;j++){
            G[i][j] = 0;
        }
    }

    scanf("%d",&n);
    for(i=0 ; i < n ; i++){
        scanf("%d %d",&u,&k);
        if(k>0){
            for(j=0;j<k;j++){
                scanf("%d",&x);
                G[u][x]=1;
            }
        }
    }

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			printf("%d", G[i][j]);
			if (j != n)printf(" ");
		}
		printf("\n");
	}
	return 0;
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {

	int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
	string ans = "";
	int u1 = ty - sy;
	int r1 = tx - sx;
	int tmp_u1;
	int tmp_r1;
	tmp_u1 = u1;
	tmp_r1 = r1;
	while (tmp_u1--) {
		ans += "U";
	}
	while (tmp_r1--) {
		ans += "R";
	}
	tmp_u1 = u1;
	tmp_r1 = r1;
	while (tmp_u1--) {
		ans += "D";
	}
	while (tmp_r1--) {
		ans += "L";
	}
	int l2 = 1;
	int u2 = u1 + 1;
	int r2 = r1 + 1;
	int d2 = 1;
	int tmp_l2;
	int tmp_u2;
	int tmp_r2;
	int tmp_d2;
	tmp_l2 = l2;
	tmp_u2 = u2;
	tmp_r2 = r2;
	tmp_d2 = d2;
	while (tmp_l2--) {
		ans += "L";
	}
	while (tmp_u2--) {
		ans += "U";
	}
	while (tmp_r2--) {
		ans += "R";
	}
	while (tmp_d2--) {
		ans += "D";
	}
	tmp_l2 = l2;
	tmp_u2 = u2;
	tmp_r2 = r2;
	tmp_d2 = d2;
	while (tmp_l2--) {
		ans += "R";
	}
	while (tmp_u2--) {
		ans += "D";
	}
	while (tmp_r2--) {
		ans += "L";
	}
	while (tmp_d2--) {
		ans += "U";
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
	int N;
  cin >> N;
  vector<int> P(N);
  for(int i = 0; i < N; i++){
    cin >> P.at(i);
  }
  vector<int> Q = P;
  vector<int> R = P;
  sort(P.begin(), P.end());
  if(P == Q){
    cout << "YES" << endl;
    return 0;
  }
  for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N; j++){
      swap(Q.at(i), Q.at(j));
      if(P == Q){
        cout << "YES" << endl;
        return 0;
      }
      swap(Q.at(i), Q.at(j));
    }
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, A, B;
  cin >> N >> A >> B;
  int P_1 = A*N;
  if (P_1 > B){
    cout << B << endl;
  }
  else{
    cout << P_1 << endl;
  }
}


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

int main() {
  int N,M,Q;
  cin>>N>>M>>Q;
  vector<vector<int>> p(Q,vector<int>(4));
  for(int i=0;i<Q;i++){
    for(int j=0;j<4;j++) cin>>p[i][j];
  }
  long long ans=0;
  vector<int> x(10);
  for(int a1=1;a1<=M;a1++){ x[0]=a1;
    for(int a2=a1;a2<=M;a2++){ x[1]=a2;
      for(int a3=a2;a3<=M;a3++){ x[2]=a3;
        for(int a4=a3;a4<=M;a4++){ x[3]=a4;
          for(int a5=a4;a5<=M;a5++){ x[4]=a5;
            for(int a6=a5;a6<=M;a6++){ x[5]=a6;
              for(int a7=a6;a7<=M;a7++){ x[6]=a7;
                for(int a8=a7;a8<=M;a8++){ x[7]=a8;
                  for(int a9=a8;a9<=M;a9++){ x[8]=a9;
                    for(int a10=a9;a10<=M;a10++){ x[9]=a10;
		long long sum=0;
    for(int i=0;i<Q;i++){
      if(x[p[i][1]-1]-x[p[i][0]-1]==p[i][2]) sum+=p[i][3];
    }
	ans=max(ans,sum);
                                              }
                                         }
                                       }
                                     }
                                   }
                                 }
                               }
                             }
                           }
                         }
 cout<<ans<<endl; 
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i, j) FOR(i, 0, j)
#define FOR(i, j, k) for(int i = j; i < k; ++i)

using namespace std;

int main(){
  int n, L[2], D[2], M[2], hh, mm, MM;
  while(scanf("%d", &n) && n){
    L[0] = L[1] = D[0] = D[1] = M[0] = M[1] = 0;
    rep(i, n){
      scanf("%d:%d%d", &hh, &mm, &MM);
      if(hh == 15 || hh == 16 || hh == 17) continue;
      if(hh == 11 || hh == 12 || hh == 13 || hh == 14){
	L[0]++;
	if((MM < mm?MM+60:MM) - mm <= 8) L[1]++;
      }else if(hh == 18 || hh == 19 || hh == 20){
	D[0]++;
	if((MM < mm?MM+60:MM) - mm <= 8) D[1]++;
      }else if(hh == 21 || hh == 22 || hh == 23 || hh == 0 || hh == 1){
	M[0]++;
	if((MM < mm?MM+60:MM) - mm <= 8) M[1]++;
      }
    }
    printf("lunch ");
    if(L[0]) printf("%d\n", L[1] * 100 / L[0]);
    else puts("no guest");
    printf("dinner ");
    if(D[0]) printf("%d\n", D[1] * 100 / D[0]);
    else puts("no guest");
    printf("midnight ");
    if(M[0]) printf("%d\n", M[1] * 100 / M[0]);
    else puts("no guest");
  }
  return 0;
}

Measured memory_bytes: 1040
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

int main() {
  int n;
  scanf("%d", &n);
  vi a(n);
  rep (i, n) {
    scanf("%d", &a[i]);
  }

  vi ind;
  if (n % 2 == 0) {
    for (int i = n; i > 1; i -= 2) {
      ind.push_back(i);
    }
    for (int i = 1; i < n; i += 2) {
      ind.push_back(i);
    }
  } else {
    for (int i = n; i >= 1; i -= 2) {
      ind.push_back(i);
    }
    for (int i = 2; i < n; i += 2) {
      ind.push_back(i);
    }
  }
  vi b;
  rep (i, n) {
    b.push_back(a[ind[i] - 1]);
  }
  rep (i, n) {
    printf("%d ", b[i]);
  }
  printf("\n");

  return 0;
}


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

int n;
int a[100000];
int m = 1000000007;
int ans = 1;

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

	if(n % 2 == 0){
		for(int i=0; i<n/2; i++){
			int t = 2 * i + 1;
			if(a[t] == 2) ans *= 2;
			else ans *= 0;
			ans %= m;
		}
	}
	if(n % 2 == 1){
		if(a[0] != 1) ans *= 0;
		for(int i=1; i<(n+1)/2; i++){
			int t = 2 * i;
			if(a[t] == 2) ans *= 2;
			else ans *= 0;
			ans %= m;
		}
	}

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

Measured memory_bytes: 512
function Main(input) {
	input = input.trim();
  var t1 = new RegExp(/^keyence$/).exec(input);
  var t2 = new RegExp(/^keyence/).exec(input);
  var t3 = new RegExp(/keyence$/).exec(input);
  var t4 = new RegExp(/^k.*eyence$/).exec(input);
  var t5 = new RegExp(/^ke.*yence$/).exec(input);
  var t6 = new RegExp(/^key.*ence$/).exec(input);
  var t7 = new RegExp(/^keye.*nce$/).exec(input);
  var t8 = new RegExp(/^keyen.*ce$/).exec(input);
  var t9 = new RegExp(/^keyenc.*e$/).exec(input);
  if(!t1 && !t2 && !t3 && !t4 && !t5 && !t6 && !t7 && !t8 && !t9){
     console.log("NO");
     }else{
     console.log("YES");
     }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define endl '\n';
#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll POSITIVE_INFINITY = 9223372036854775807;
const ll NEGATIVE_INFINITY = -9223372036854775807;
const ll MOD = 1000000007;
const ld PI = acos(-1.0);

template <typename T> inline T bigMod(T A,T B,T M = MOD){A %= M;T ret = 1;while(B){if(B & 1) ret = (ret * A) % M;A = (A * A) % M;B = B >> 1;}return ret;}
template <typename T> inline T invMod (T A,T M = MOD){return bigMod(A,M-2,M);}

const int N = 200005;

int main(){
  FASTER;
  int n, k;
  cin >> n >> k;
  vector<int>vis(10, 0);
  for (int i = 0; i < k; i++){
    int x;
    cin >> x;
    vis[x] = 1;    
  }
  auto ok = [&] (int x){
    while (x > 0){
      int d = x % 10;
      if (vis[d] == 1){
        return false;
      }
      x /= 10;
    }
    return true; 
  };
  while (true){
    if (ok(n)){
      cout << n << "\n";
      return 0;
    }
    n++;
  } 
  return 0;
}

Measured memory_bytes: 256