akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string, string> P;

string s;

void dfs(int i, int end, const string lTemp, const string rTemp, vector<P> &x)
{
    if (i == end)
    {
        x.push_back(make_pair(lTemp, rTemp));
        return;
    }

    dfs(i + 1, end, lTemp + s[i], rTemp, x);
    dfs(i + 1, end, lTemp, s[i] + rTemp, x);
}

bool compare(const P l, const P r)
{
    return l.first == r.first ? l.second < r.second : l.first < r.first;
}

int main(void)
{
    int n;
    cin >> n;
    cin >> s;
    reverse(s.begin() + n, s.end());

    vector<P> vl;
    vector<P> vr;
    dfs(0, n, "", "", vl);
    dfs(n, 2 * n, "", "", vr);
    sort(vl.begin(), vl.end());
    sort(vr.begin(), vr.end());

    long long score = 0;
    for (auto ia = vl.begin(); ia < vl.end(); ++ia)
    {
        auto ib_upper = upper_bound(vr.begin(), vr.end(), *ia);
        auto ib_lower = lower_bound(vr.begin(), vr.end(), *ia);
        score += ib_upper - ib_lower;
    }

    cout << score << endl;
    return 0;
}


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

int selection_sort(int a[], int n){
    int sw = 0;
    for(int i = 0; i < n-1; i++){
        int mini = i;
        for(int j = i; j < n; j++){
            if(a[mini] > a[j]) mini = j;
        }
        std::swap(a[mini], a[i]);
        if (mini != i) sw++;
    }
    return sw;
}

int main(void){
    int n;
    std::cin >> n;

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

    int swap_number = selection_sort(a, n);

    for(int i = 0; i < n; i++){
        if(i != n-1){
            std::cout << a[i] << " ";
        }
        else{
            std::cout << a[i] << std::endl;
        }
    }
    std::cout << swap_number << std::endl;
    return 0;
}


Measured memory_bytes: 3100
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]){
	int N;
	cin >> N;

	int sum=0;
	int ans = 0;
	for(int x=0; 4*x<=N; x++){
		for(int y=0; 7*y<=N; y++){
			sum = 4*x + 7*y;
			if(sum==N){
				ans++;
				break;
			}
		}
		if(ans>0) break;
	}
	if(ans){printf("Yes\n");}
	else{printf("No\n");}
	return 0;
}

Measured memory_bytes: 256
import Data.List
main = getContents >>= mapM_ (putStrLn . fout . is_it_a_right_triangle . fin) . tail . lines
fin = sort . map read . words
fout p = if p then "YES" else "NO"

is_it_a_right_triangle [x,y,z] = x^2 + y^2 == z^2

Measured memory_bytes: 4192
#pragma region include
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstdio>
#include <tuple>
//#define int ll
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)
#define MOD 1000000007
#define INF 1000000000
#define LLINF 4000000000000000000
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
void input() {}
template<typename F, typename... R>void input(F& f, R&... r) { cin >> f; input(r...); }
template<typename F, typename... R>void input(vector<F>& f, R&... r) { REP(i, f.size())input(f[i]); input(r...); }
#pragma endregion

signed main() {
    int N; cin >> N;
    map<pair<ll,ll>,int> mp;
    vector<ll> x(N), y(N);
    REP(i, N) {
        cin >> x[i] >> y[i];
    }
    REP(i, N) {
        REP(j, N) {
            if (i != j) mp[pair<ll, ll>(x[i] - x[j], y[i] - y[j])]++;
        }
    }
    int ans = 0;
    for (auto p : mp) {
        ans = max(ans, p.second);
    }
    cout << N - ans << endl;
    getchar(); getchar();
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}

void mainsolve(){

	ll n,m;
	cin >> n >> m;
	vector<ll> pen(n);
	vector<bool> isAC(n,false);

	rep(i,m){
		ll p;
		string s;
		cin >> p >> s;
		--p;
		if(s == "AC"){
			isAC[p] = true;
		}
		else{
			if(!isAC[p]) pen[p]++;
		}
	}

	ll res1 = 0;
	ll res2 = 0;

	rep(i,n){
		if(isAC[i]) res1++;
	}

	rep(i,n){
		if(isAC[i]) res2 += pen[i];
	}
	cout << res1 << " " << res2 << endl;
	return;
}

int main(){
	
	//ll TC;cin>>TC;rep(I,TC){cout<<"case:"<<I+1<<"---"<<endl; // comment out!
		mainsolve();
	//} // comment out!
	return 0;
}

Measured memory_bytes: 1024
n,k = map(int, input().split())
s = 0
for i in range(1000):
    if 2**i <= k < 2**(i+1):
        s = i+1
        break
t = 0
for i in range(n):
    if s == 0 and k<=n:
        t+=1
        
    elif k<=(i+1) *2**s and k> (i+1) *2**(s-1):
        t+=1/(2**s)
    else:
        s-=1
        t+=1/(2**s)
print(t/n)

Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
# edge-bitset of each set of constraints
edgest = [0] * 2**m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            edgest[1 << i] |= (1 << edge_dict[(uu, vv)])
for i in range(1, 2**m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]
 
# dp[set of constraints]
dp = [0] * 2**m
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    limit_num = bin(edgest[i] ^ edgest[i ^ lsb]).count("1")
    dp[i] = dp[i ^ lsb] >> limit_num
    # Inclusion and exclusion
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

Measured memory_bytes: 59356
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func main() {
	sc.Split(bufio.ScanWords)
	N, M := getInt(), getInt()
	a := make([]int, M)
	sum := 0
	for i := 0; i < M; i++ {
		a[i] = getInt()
		sum += a[i]
	}

	out(max(-1, N-sum))
}


Measured memory_bytes: 1876
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define DEB(variable) cout << #variable << '=' << variable << endl

#define FOR(LoopVariable, numberOFbegin, numberOFend) for(long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable, numberOFbegin, numberOFend) for(long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable, numberOFend) for(long long int LoopVariable = 0; (LoopVariable) < (numberOFend); LoopVariable++)

using llint = long long int;

constexpr long long int linf = numeric_limits<long long int>::max() - 5;
constexpr long long int inf = numeric_limits<int>::max() - 5;

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while(n > 0) {
        if(n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
vector<llint> make_stringhash(string s, llint search_size) {
    vector<llint> result;
    if(s.size() < search_size) {
        return result;
    }
    llint tmphash = 0;
    REP(i, search_size - 1) {
        tmphash = tmphash * 97 + (llint)s[i];
        tmphash %= 2147483647;
    }
    FOR(i, search_size - 1, s.size()) {
        tmphash = tmphash * 97 + (llint)s[i];
        tmphash %= 2147483647;
        result.push_back(tmphash);
        //   cout << tmphash << endl;
        tmphash -= s[i - search_size + 1] * modpow(97, search_size - 1, 2147483647);
        while(tmphash < 0) {
            tmphash = (tmphash +100ll* 2147483647ll);
        }
        tmphash = (tmphash + 2147483647) % 2147483647;
    }
    return result;
}

int main() {
    string s, t;
    cin >> s >> t;
    vector<llint> hash = make_stringhash(s, t.size());
    llint thash = 0;
    REP(i, t.size()) {
        thash = thash * 97 + (llint)t[i];
        thash %= 2147483647;
    }
    //  cout << thash << endl;

    REP(i, hash.size()) {
        if(thash == hash[i]) {
            if(1 /*s.substr(i, t.size()) == t*/) {
                cout << i << endl;
            }
        }
    }
}


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

int main(){
  int n,count;
  char ch[201];

  while(cin>>n){
    if(n==0)break;
    n=2*n;
    count=0;
    for(int i=0;i<n;i++)
      cin>>ch[i];

    for(int i=0;i+3<n;i++)
      if((ch[i]=='l' && ch[i+1]=='u')&&(ch[i+2]=='r' && ch[i+3]=='u'))count++;
      else if((ch[i]=='l' && ch[i+1]=='d')&&(ch[i+2]=='r' && ch[i+3]=='d'))count++;
      else if((ch[i]=='r' && ch[i+1]=='u')&&(ch[i+2]=='l' && ch[i+3]=='u'))count++;
      else if((ch[i]=='r' && ch[i+1]=='d')&&(ch[i+2]=='l' && ch[i+3]=='d'))count++;
    cout<<count<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<cassert>
using namespace std;
string S;
int cur;
int pqr[3];
int deny[3]={2,1,0};
int multi[3][3]={{0,0,0},{0,1,1},{0,1,2}};
int sum[3][3]={{0,1,2},{1,1,2},{2,2,2}};
int formula();
int Deny(int );
int main(){
  while(cin>>S&&S!="."){
    int cnt=0;
    for(int p=0;p<=2;p++){
      for(int q=0;q<=2;q++){
        for(int r=0;r<=2;r++){
          cur=0;
          pqr[0]=p;pqr[1]=q;pqr[2]=r;
          if(formula()==2)cnt++;
        }
      }
    }
    cout<<cnt<<endl;
  }
}
int formula(){
  if('0'<=S[cur]&&S[cur]<='2'){
    return (int)(S[cur++]-'0');
  }else if('P'<=S[cur]&&S[cur]<='R'){
    return pqr[(int)(S[cur++]-'P')];
  }else if(S[cur]=='-'){
    cur++;
    return Deny(formula());
  }else{
    assert(S[cur++]=='(');
    int left=formula();
    char op=S[cur++];
    // cout<<"op=="<<op<<endl;
    assert(op=='+'||op=='*');
    
    int right=formula();
    assert(S[cur]==')');
    cur++;
    return (op=='+')?sum[left][right]:multi[left][right];
  }
}
int Deny(int a){
  assert(0<=a&&a<=2);
  return deny[a];
}

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

int main(){
	
	double a,b,x;
	cin>>a>>b>>x;
	double val,x1=(a*a*a);
	if(x>(a*a*b)/2.0)
	{
		val=atan2((2.0*a*a*b-2*x),x1);
		cout<<setprecision(12)<<(val*180.00)/3.141592653;
	}
	else
	{
		val=atan2((a*b*b),2*x);
		cout<<setprecision(12)<<(val*180.00)/3.141592653;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<char,int> pci;
typedef vector<pair<int,int>> vpii;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
#define sci(a) scanf("%d",&a)
#define scii(a,b) scanf("%d %d",&a,&b)
#define sciii(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sciiii(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define scl(a) scanf("%lld",&a)
#define scll(a,b) scanf("%lld %lld",&a,&b)
#define sclll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c
#define scllll(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define print(a) printf("%d ",a)
#define println(a) printf("%d\n",a)
#define ln printf("\n")
#define pb(a) push_back(a)
#define m_p(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define rep(i,s,n) for(int i=s;i<=n;i++)
#define rrep(i,e,s) for(int i=e;i>=s;i--)
#define repv(i,m) for(auto i = m.begin();i != m.end();i++)
#define FileIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const long long INF = 4000000000000000000LL;
/************************************* Chocolate *************************************/
const int mod = 1e9+7;
int main(){
    int n;
    string s;
    sci(n);
    cin >> s;
    s = " "+ s;
    vvi dp(n+1,vi(n+1,0)); //dp[i][j] = #of permutations of size 'i' with first i numbers where last element is 'j'.
    dp[1][1] = 1;
    vi prev(n+1,0);
    prev[1] = 1;
    rep(i,1,n-1){
        vi now(n+1,0);
        rep(j,1,i+1){
            if(s[i] == '>')
                dp[i+1][j] = (prev[i] - prev[j-1] + mod)%mod;
            else
                dp[i+1][j] = prev[j-1];
            now[j] = (now[j-1] + dp[i+1][j])%mod;
        }
        prev = now;
    }
    cout << prev[n] << endl;
}

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

template<typename T>
T get_value(std::istream& is);

int main() {
  vector<int> v(get_value<size_t>(cin));
  for (auto& e: v)
    cin >> e;

  auto count {0u};
  while(all_of(v.begin(), v.end(), [](auto e){return !(e%2);})) {
    ++count;
    for (auto&e : v)
      e /= 2;
  }
  cout << count << '\n';
  return 0;
}

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


Measured memory_bytes: 384
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<String> arr1 = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			arr1.add(sc.next());
		}
		ArrayList<String> arr2 = new ArrayList<>();
		for(int i = 0; i < m; i++) {
			arr2.add(sc.next());
		}
		for(int i = 0; i <= n - m; i++) {
			for(int j = 0; j <= n - m; j++) {//座標の右上を全探索

				for(int k = 0; k < m; k++) {
					if(arr1.get(i+k).substring(j).startsWith(arr2.get(k))) {
						if(k == m - 1) {
							System.out.println("Yes");
							return;
						}
					} else {
						break;
					}
				}

			}
		}
		System.out.println("No");
	}
}


Measured memory_bytes: 23380
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main(void){
    while(1){
        int n;
        cin>>n;
        if(n==0)break;
        vector<int> a(n+1);
        int sum=0;
        for(int i=0;i<=n;i++){
            sum+=i;
            a[i]=sum;
        }
        int ans=0;
        for(int i=0;i<=n;i++){
            for(int j=i;j<=n;j++){
                if(a[j]-a[i]==n)ans++;
            }
        }
        cout<<max(ans-1,0)<<endl;
    }
    return 0;
}



Measured memory_bytes: 3052
s=input()
for c in s:
	if (not ('a'<=c and c<='z')) and (not(c=='A' or c=='C')):
		print("WA")
		exit(0)
if s[0]!='A':
	print("WA")
	exit(0)
if s[2:len(s)-1].count('C')!=1:
	print("WA")
	exit(0)
print("AC")


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

int main(){
  int N, M, ans;
  cin >> N >> M;
  
  ans = (N - M)*100 + M*1900;
  for (int i = 0; i < M; i++){
    ans *= 2;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3548
//#pragma GCC optimize ('O3')
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define pb push_back

const int N = 2e5 + 5;
const int M = 5e5 + 5;
const int OO = 1e9;
const int mod = 1e9 + 7;

int n,k,a[N],I1=-1,I2=-1,J1=-1,J2=-1;
ll ans=1;

void init() {}

int mul(int a, int b) {

    a = (a + mod) % mod;
    b = (b + mod) % mod;
    return (1LL*a*b)%mod;

}

ll solve1() {

    for (int i = k-1; ~i ; --i) {
        if(a[i]<0) {
            I1 = i;
            break;
        }
    }

    for (int i = k; i < n; ++i) {
        if(a[i]>=0) {
            J1 = i;
            break;
        }
    }

    if(I1 == -1 || J1 == -1) return -1;

    int ret = a[J1];

    for (int i = 0; i < k; ++i) {
        if(i!=I1) ret = mul(ret, a[i]);
    }

    return ret;

}

ll solve2() {

    for (int i = k-1; ~i ; --i) {
        if(a[i]>=0) {
            I2 = i;
            break;
        }
    }

    for (int i = k; i < n; ++i) {
        if(a[i]<0) {
            J2 = i;
            break;
        }
    }

    if(I2 == -1 || J2 == -1) return -1;

    int ret = a[J2];

    for (int i = 0; i < k; ++i) {
        if(i!=I2) ret = mul(ret, a[i]);
    }

    return ret;

}

int main() {

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

    cin >> n >> k;

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

    sort(a,a+n, [](int a, int b){
        return abs(a)<abs(b);
    });
    reverse(a, a+n);

    int cnt = 0;

    for (int i = 0; i < k; ++i) {
        cnt += (a[i]<0);
    }

    if(cnt&1) {

        ll a1 = solve1();
        ll a2 = solve2();

        if(a1==-1 && a2==-1) {

            for (int i = n-1; i > n-1-k; --i) {
                ans = mul(ans, a[i]);
            }

            cout << ans << '\n';

        } else if(a1==-1) cout << a2 << '\n';
        else if(a2==-1) cout << a1 << '\n';
        else if(1LL*a[J1]*a[I2]>1LL*a[J2]*a[I1]) cout << a1 << '\n';
        else cout << a2 << '\n';

    } else {
        for (int i = 0; i < k; ++i) {
            ans = mul(ans, a[i]);
        }

        cout << ans << '\n';

    }

    return 0;
}

Measured memory_bytes: 4432
#include <stdio.h>

int main() {
  int N,M,result=0;
  scanf("%d %d",&N,&M);
  if(N>=2) {
    while(N!=0) {
      N--;
      result+=N;
    }
  }
  if(M>=2) {
    while(M!=0) {
      M--;
      result+=M;
    }
  }
  printf("%d",result);
  return 0;
}

Measured memory_bytes: 1728
import java.util.PriorityQueue;
import java.util.Scanner;

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

		PriorityQueue<Long> left = new PriorityQueue<>(n);
		long[] center = new long[n];
		PriorityQueue<Long> right = new PriorityQueue<>((l1, l2) -> {
			return l2.compareTo(l1);
		});

		for (int i = 0; i < n; i++) {
			left.add(sc.nextLong());
		}
		for (int i = 0; i < n; i++) {
			center[i] = sc.nextLong();
		}
		for (int i = 0; i < n; i++) {
			right.add(sc.nextLong());
		}

		long[] lmove = new long[n + 1];
		lmove[0] = left.stream().mapToLong(i -> i).sum();
		long[] rmove = new long[n + 1];
		rmove[0] = right.stream().mapToLong(i -> i).sum();

		for (int i = 0; i < n; i++) {
			left.add(center[i]);
			lmove[i + 1] = lmove[i] - left.poll() + center[i];
		}
		for (int i = 0; i < n; i++) {
			right.add(center[n - 1 - i]);
			rmove[i + 1] = rmove[i] - right.poll() + center[n - 1 - i];
		}

		long ans = Long.MIN_VALUE;
		for (int i = 0; i <= n; i++) {
			long temp = lmove[i] - rmove[n - i];
			ans = Math.max(temp, ans);
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 101608
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
aa = list(set(a))
aa.sort()
compress = {aa[i]: i for i in range(len(aa))}
cnt = [0] * len(aa)
idx = [-1] * len(aa)
for i in range(N)[::-1]:
    n = compress[a[i]]
    cnt[n] += 1
    idx[n] = i
ans = [0] * N
for n in range(1, len(aa))[::-1]:
    i = idx[n]
    ans[i] += cnt[n] * (aa[n] - aa[n-1])
    cnt[n-1] += cnt[n]
    idx[n-1] = min(idx[n-1], i)
ans[0] += N * aa[0]
print(*ans, sep='\n')

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

int main() {
  int x,a,b;
  cin>>x>>a>>b;

  if (a-b>=0) cout<<"delicious"<<endl;
  else if (b-a<=x) cout<<"safe"<<endl;
  else cout<<"dangerous"<<endl;
  return 0;
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
#define LL long long
#define MOD 1000000007

//cout << (c)?"Yay!":":(" << endl;

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    int num = a;
    int count = 1;
    if (b == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    while (num < b)
    {
        num += a - 1;
        count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <string.h>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;
int main(){
    int N,M,count=0;
    cin >> N >> M;
    int K[M],dis[M-1];
    for(int i=0;i<M;i++){
        cin >> K[i];
    }
    if(N>=M){
        count=0;
    }else{
        sort(K,K+M);
        for(int i=0;i<M-1;i++){
            dis[i]=K[i+1]-K[i];
        }
        sort(dis,dis+M-1,greater<int>());
        for(int i=N-1;i<M-1;i++){
            count = count + dis[i];
        }
    }
    cout << count << endl;   
}

Measured memory_bytes: 1024
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
using namespace std;

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

int main() {
	long N,K,X;
	X = 0;
	cin >> N >> K;
	vector<int> H(N);
	rep(i, N)
		cin >> H[i];
	sort(H.begin(), H.end());
	rep(i, N - K)
		X += H[i];
	cout << X;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s, n) for(int i = s; i < (int)(n); i++)
#define co(x) cout<<x<<endl
#define SQvec(i,j) vector<vector<int>> data(i, vector<int>(j))
#define mod 1000000000+7
typedef long long int lint;

int main() {
  lint N,ans = 0;
  cin >> N;
  vector<int> a(N);
  rep(i,0,N){cin >> a[i];}
  
  rep(i,0,N){
    ans += a[i];
  }
  co(ans - N);
}

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

using namespace std;

typedef long long ll;

int main(){
  ll l,r;
  cin>>l>>r;
  int ans=2018;
  r = min(r,l+4038);
  for(ll i=l;i<=r;i++){
    for(ll j=i+1;j<=r;j++){
      int x = i*j%2019;
      ans=min(ans,x);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
G = [[] for _ in range(N)]
H = []
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append([b,i]);G[b].append([a,i]) #iを辺のIDとして保存
  H.append([a,b])
ans = 0

def dfs(v,ID): #IDの辺を使えない
  visited.add(v)
  for u,idx in G[v]:
    if idx == ID or u in visited:
      continue
    dfs(u,ID)

for i in range(M):
  visited = set([])
  start = H[i][0]
  goal = H[i][1]
  dfs(start,i)
  if goal not in visited:
    ans +=1
print(ans)
  

Measured memory_bytes: 9228
import std.stdio,std.string,std.conv;

int main()
{
	string s;
	while((s = readln.chomp).length != 0)
	{
		string[] _s = s.split(",");
		int values[11];
		double v[2];

		values[0] = 0;
		foreach(i;1..11) values[i] = _s[i-1].to!int + values[i-1];
		foreach(i;0..2)	v[i] = _s[i+10].to!int;	

		double temp = v[0] / (v[0] + v[1]);
		temp *= values[10];
		bool flag = true;

		foreach(i;0..10)
		{
			if(values[i] <= temp && temp <= values[i+1] && flag)
			{
				writeln(i+1);
				flag = false;
			}
		}

	}
	return 0;
}

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

int main(){
    int A, B, C, N, M ,K;
    int sum = 0;
    int t = 0;
    string s, s1;
    cin >> A >> B >> C;
    if(A==B && B==C) cout << "Yes" << endl;
    else cout << "No" << endl;
//    vector<int> X();

//    for(int i = 0; i < ; i++){}
//    for(int j = 0; j < ; j++){}

//    cout <<  << endl;
}

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

int main()
{
   int t1;
   cin>>t1;
   int a=0,t=0,w=0,r=0;
   vector<string>v;
   while(t1--)
   {
       string s;
       cin>>s;
      // v.push_back(s);
      if(s=="AC"){
        a++;
      }
      else if(s=="WA"){
        w++;
      }
      else if(s=="RE"){
        r++;
      }
      else{
        t++;
      }
   }

   cout<< "AC x "<<a<<endl;
   cout<< "WA x "<<w<<endl;
   cout<< "TLE x "<<t<<endl;
   cout<< "RE x "<<r<<endl;

}






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

using namespace std;
int an[3];


int main()
{
    int sizea,sizeb;
    cin>>sizea>>sizeb;
    an[0] = sizea+sizea-1;
    an[1] = sizea+sizeb;
    an[2] = sizeb+sizeb-1;
    sort(an,an+3);
    cout<<an[2]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1, (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int digit(ll a){
    int d = 0;
    while(a > 0){
        a /= 10;
        d++;
    }
    return d;
}

int main(){
    ll n;
    cin >> n;
    int ans = 1e9;
    for(ll i=1; i*i<=n; i++){
        if(n%i == 0){
            ans = min(ans, digit(n/i));
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//変数//
		int H;		//縦ピクセル数
		int W;		//横ピクセル数
		
		String[] C;		//入力されたピクセル
		
		Scanner scan = new Scanner(System.in);
		
		//入力//
		H = scan.nextInt();
		W = scan.nextInt();
		
		C = new String[H];
		for(int i = 0; i < H; i++ ){
			C[i] = new String(scan.next());
		}
		
		scan.close();
		
		//処理//
		//結果//
		for(int i = 0; i < H; i++){
			System.out.println(C[i]);
			System.out.println(C[i]);
		}
		
	}
	
}


Measured memory_bytes: 11684
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  h,w,d  = (int(i) for i in input().split())
  a = []
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      number = a[i][j] - 1
      query[number] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)
  
  for i in range(q):
    l,r = (int(m) for m in input().split())
    print(distance[r-1]-distance[l-1])
  
solve()

Measured memory_bytes: 57308
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PI 				acos(-1)
#define mp				make_pair
#define pb				push_back
#define all(a)			(a).begin(), (a).end()
#define srt(a)			sort(all(a))
#define mem(a, h)		memset(a, (h), sizeof(a))
#define f 				first
#define s 				second
#define MOD				1000000007
#define MOD1			998244353
#define EPS				1e-9
#define fore(i, b, e)	for(int i = b; i < e; i++)
#define forg(i, b, e, m)	for(int i = b; i < e; i+=m)
int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
using namespace __gnu_pbds;

typedef long long 		ll;
typedef unsigned long long 		ull;
typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int tam = 10000010;
int sus[2][100010];
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	//freopen("qwe.txt", "r", stdin);
	//freopen("asd.txt", "w", stdout);
	int n, m;
	string s;
	cin>>n>>m>>s;
	fore(i, 2, n+1)
		sus[0][i] = sus[0][i-1] + (s[i-1] == 'C' && s[i-2] == 'A');
	fore(i, 1, n)
		sus[1][i] = sus[1][i-1] + (s[i-1] == 'A' && s[i] == 'C');
	fore(i, 0, m)
	{
		int l, r;
		cin>>l>>r;
		cout<<sus[0][r] - sus[1][l-1]<<'\n';
	}
	return 	0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS2

Measured memory_bytes: 1872
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl lcm(intl a,intl b){
    return a / gcd(a, b) * b;
}
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl p[n];
    cin(i,p);
    intl cnt = 0;
    rep(i,n){
        cnt += (p[i] != 1 + i);
    }
    fp(cnt <= 2,"YES","NO");
    return 0;
}

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

int main(){
	string str;
	cin >> str;
	for(int i = 0; i < str.size(); i++){
		if(str[i]-3-'A' < 0) str[i] = str[i]-3+26;
		else str[i] = str[i]-3;
	}
	cout << str << endl;
}

Measured memory_bytes: 1180
a, b = [int(item) for item in input().split()]

if b == a:
  print(a)
elif (b - a) == 1:
  print(b ^ a)
else:
  if (a%2==0):
    first = a
    c = 0
  else:
    first = a + 1
    c = a
  if (b%2==1):
    last = b
    d = 0
  else:
    last = b-1
    d = b
  e = 1 if (last - first) % 4 == 1 else 0

  print(c ^ d ^ e)

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

using namespace std;

#define N 2200

int n,a[N],b[N][N],d[N];
bool vis[N];
vector<int> g[N];
priority_queue<int> pq;

void dfs(int u){
	vis[u]=1;
	for (int v=1;v<=n;++v)
		if (!vis[v]&&b[u][v]){
			g[u].push_back(v); ++d[v];
			dfs(v);
		}
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",a+i);
	sort(a+1,a+n+1);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j) b[i][j]=__gcd(a[i],a[j])>1;
	for (int i=1;i<=n;++i) if (!vis[i]) dfs(i);
	for (int i=1;i<=n;++i) if (!d[i]) pq.push(i);
	for (int i=1;i<=n;++i){
		int x=pq.top(); pq.pop();
		printf(i==n?"%d\n":"%d ",a[x]);
		for (int y:g[x]){
			--d[y];
			if (!d[y]) pq.push(y);
		}
	}
	
	return 0;
}
			

Measured memory_bytes: 18944
N,M = map(int, input().split())
count = [0 for i in range(N+1)] #0-N番の道路の個数（０番目は使用しないように注意)

for i in range(M):
    a,b = map(int, input().split())
    count[a]+=1
    count[b]+=1

for i in range(1,N+1):
    print(count[i])
    

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

using namespace std;

int main(void)
{
    string str;
    cin>>str;
    map<string,int>m;
    string a="maerd";
    m[a]=true;
    a="remaerd";
    m[a]=true;
    a="esare";
    m[a]=true;
    a="resare";
    m[a]=true;
    a.clear();
    int counter=0;
    for(int i=str.size()-1;i>=0;i--){
        a+=str[i];
        if(a.size() > 7)break;
        if(m[a]==true){
            counter+=a.size();
            a.clear();
        }
    }
    if(counter==str.size())printf("YES\n");
    else printf("NO\n");

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
    string S;
    cin >> S;
    string T = S;
    reverse (T.begin(),T.end());
    int A = 0;
    for(int i = 0; i < S.size(); i++){
        for(int j = 0; j < T.size(); j++){
            if(i == j && S.at(i) != T.at(j)){
                A++;
            }
        }
    }
    cout << A / 2 << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// スペース区切りの整数の入力
		int seep = sc.nextInt();
		int wolf = sc.nextInt();
		// 出力
		System.out.println(wolf >= seep ? "unsafe" : "safe ");
	}
}

Measured memory_bytes: 35700
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353LL;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n, k;
int a[N];
ll cal(double up, double goal)
{
    ll ret = 0;
    ret += floor(up / goal - 1e-9);
    return ret;
}

bool check(double x)
{
    ll sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        sum += cal(a[i], x);
        if (sum > k)
            return 0;
    }
    return 1;
}

void solve()
{
    cin >> n >> k;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), ans = max(ans, a[i]);
    double l = 1e-9, r = ans;
    int tot = 100;
    while (tot--)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid, ans = ceil(mid);
        else
            l = mid;
    }
    printf("%d\n", ans);
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

Measured memory_bytes: 4604
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>

using namespace std;

int main()
{
  int cnt = 1;
  int x;
  while(true)
  {
    cin >> x;
    if(!x)
      break;
    cout << "Case " << cnt << ": " << x << endl;
    cnt++;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n; cin>>n;
    vector<int> p(n);
    for(int i=0;i<n;i++) cin>>p[i];
    int maxp=0;
    int maxin=0;
    for(int i=0;i<n;i++){
        if(p[i]>maxp){
            maxp=p[i];
            maxin=i;
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(i!=maxin) ans+=p[i];
    }
    cout<<ans+maxp/2<<endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
cnt=0
for i in range(n):
  if a[i]>=b[i]:
    cnt+=b[i]
  else:
    if a[i]+a[i+1]<b[i]:
      cnt+=a[i]+a[i+1]
      a[i+1]=0
    else:
      a[i+1] =-b[i]+a[i]+a[i+1]
      cnt+=b[i]
print(cnt)

Measured memory_bytes: 24340
n, m = map(int, input().split())
k = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
answer = 0
## k = sorted(k, reverse=True, key=lambda x: len(x))

all = [] # 全てのスイッチの状態
for i in range(0, 2**n):
  all.append(list(str(format(i, 'b').zfill(n))))

for a in all:
  for index in range(len(k)):
    switch_count = 0 
    for switch in k[index]: #1,2
      if a[switch-1] == "1":
        switch_count+=1
      else:
        continue
    #一つの電球に繋がってる全てのスイッチ確認終了
    if switch_count%2 == p[index]:
      if index == len(k)-1:
      	answer+=1
      continue
    break

print(answer)
    

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

int main(){
    int n, k; scanf("%d %d", &n, &k);
    int c = (n-1)*(n-2)/2-k;
    if(c < 0) printf("%d",-1);
    else{
        printf("%d\n",c+(n-1));
        for(int i=1; i<=n-1;  i++) printf("%d %d\n",i,n);
        for(int i=1; i<=n-1; i++) for(int j=i+1; j<=n-1; j++){
            if(!c--) return 0; printf("%d %d\n",i,j);
        }
    }
}

Measured memory_bytes: 3792
import sys
from collections import deque
readline = sys.stdin.readline
dq = deque()
for _ in range(int(input())):
    c = readline().split()
    if c[0] == "deleteFirst":
        dq.popleft()
    elif c[0] == "deleteLast":
        dq.pop()
    else:
        if c[0] == "insert":
            dq.appendleft(c[1])
        elif c[0] == "delete":
            if c[1] in dq:
                dq.remove(c[1])
print(*dq)



Measured memory_bytes: 69728
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include<queue>

using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n; ++i)
#define ALL(a) (a).begin(),(a).end()
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)

int main(){
    ll n, h;
    cin >> n >> h;
    vector<ll> a(n), b(n);
    rep(i, n)cin >> a[i] >> b[i];

    sort(ALL(a), greater<ll>());
    sort(ALL(b), greater<ll>());
    
    ll res = 0;
    ll dmg = 0;
    ll i = 0;
    while(a[0] <= b[i] && i < n){
        res++;
        dmg += b[i++];
        if(dmg >= h){
            cout << res;
            return 0;
        }
    }

    while(dmg < h)res++, dmg+=a[0];
    cout << res << endl;
}

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

using namespace std;

int const INF = 1 << 30;

int const N = 223456;

unordered_map<int, vector<int> > edges[N];

unordered_map<long long, int> d;

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int v, u, c;
    scanf("%d%d%d", &v, &u, &c);
    --v;
    --u;
    edges[v][c].push_back(u);
    edges[u][c].push_back(v);
    if (c == 0) {
      while (true);
    }
  }
  set<pair<int, long long> > q;
  q.insert({0, 0});
  int ans = INF;
  while (!q.empty()) {
    pair<int, long long> z = *q.begin();
    q.erase(q.begin());
    int wh = (int) (z.second / n);
    int v = (int) (z.second % n);
    int cost = z.first;
    if (v == n - 1) {
      ans = std::min(ans, cost);
    }
    if (wh != 0) {
      {
        long long to = v;
        if (d.find(to) == d.end() || d[to] > cost + 1) {
          q.erase({d[to], to});
          d[to] = cost + 1;
          q.insert({d[to], to});
        }
      }
      if (edges[v].find(wh) != edges[v].end()) {
        auto &lst = edges[v][wh];
        for (int u : lst) {
          long long to = u + (long long) n * wh;
          if (d.find(to) == d.end() || d[to] > cost) {
            q.erase({d[to], to});
            d[to] = cost;
            q.insert({d[to], to});
          }
        }
      }
    } else {
      for (auto &pp : edges[v]) {
        auto &lst = pp.second;
        for (int u : lst) {
          long long to = u + (long long) n * pp.first;
          if (d.find(to) == d.end() || d[to] > cost) {
            q.erase({d[to], to});
            d[to] = cost;
            q.insert({d[to], to});
          }
        }
      }
    }
  }
  printf("%d\n", ans == INF ? -1 : (ans + 1));
}


Measured memory_bytes: 73588
DISCO=list(map(int,input().split()))

sum_money=0
for i in DISCO:
    if i==1:
        sum_money+=300000
    elif i==2:
        sum_money+=200000
    elif i==3:
        sum_money+=100000
if sum(DISCO)==len(DISCO):
    sum_money+=400000
print(sum_money)
        


Measured memory_bytes: 2940
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

ans=0
for i in range(m):
    unionFind=UnionFind(n+1)
    for j,k in enumerate(AB):
        a,b=k
        if i==j:continue
        else:unionFind.Unite(a,b)
    ans +=0 if unionFind.size(1)==n else 1
print(ans)

Measured memory_bytes: 42480
import itertools
N,K = map(int, input().split())
c = []
for i in range(K):
	a = int(input())
	b=list(map(int,input().split()))
	c.append(b)
f = list(itertools.chain.from_iterable(c))
d = []
for i in range(1,N+1):
	e =  i in f
	if e  == False:
		d.append(i)
length = len(d)
print(length)


Measured memory_bytes: 9104
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
int main() {
  ll n,d;
  cin>>n>>d;
  int ans=0;
  rep(i,n){
    ll x,y;
    cin>>x>>y;
    if(x*x+y*y<=d*d) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define e endl
#define MAXN 200005
#define MOD 998244353
int main()
{
     int s,w;
     cin>>s>>w;
     if(w>=s)
          cout<<"unsafe";
     else
          cout<<"safe";


}


Measured memory_bytes: 3632
#include <stdio.h>
#define LL long long
#define maxn 200010
LL k,t;
int n,a[maxn],vis[maxn];
int main(){
	int i,nx,s,b,c;
	scanf("%d%lld",&n,&k);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	nx=1;
	while(1){
		vis[nx]=1,nx=a[nx];
		if(vis[nx]){s=nx;break;}
	}
	nx=s;
	for(i=1;i<=n;i++)vis[i]=0;
	while(1){
		vis[nx]=1,nx=a[nx],t++;
		if(vis[nx])break;
	}
	b=0,nx=1;
	while(1){
		if(nx==s)break;
		nx=a[nx],b++;
	}
	c=0;
	if(k<=b){
		nx=1;
		while(1){
			if(k==c)break;
			nx=a[nx],c++;
		}
		printf("%d\n",nx);
		return 0;
	}
	k-=b;k%=t;
	{
		nx=s;
		c=0;
		while(1){
			if(k==c)break;
			nx=a[nx],c++;
		}
		printf("%d\n",nx);
	}
}

Measured memory_bytes: 4792
n, x, y = map(int, input().split())

ans = dict.fromkeys(range(1, n), 0)

for i in range(1, n+1):
    for j in range(i+1, n+1):
        d = min(abs(j - i), abs(x - i) + 1 + abs(y - j), abs(x - j) + 1 + abs(y - i))
        ans[d] += 1

for v in ans.values():
    print(v)


Measured memory_bytes: 3572
n, k = [int(i) for i in input().split()]
h = [None for i in range(n)]
for i in range(n):
  h[i] = int(input())

h = sorted(h)


min = 10 ** 9 + 1
for i in range(n - k + 1):
  h_min = h[i]
  h_max = h[i + k - 1]
  h_diff = h_max - h_min
  if h_diff < min:
    min = h_diff

print(min)

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

namespace HABIT{
    #define f(a,b,c,d) for(register int a=b,c=d;a<=c;a++)
    #define g(a,b,c,d) for(register int a=b,c=d;a>=c;a--)
    #define LOCAL
    typedef int i32;
    typedef unsigned int u32;
    typedef long long int i64;
    typedef unsigned long long int u64;
    const i32 MAXN=1024;
    typedef i32 ar[MAXN];
    
    template<typename T> inline T Max(T a) { return a; }
    template<typename T,typename... Args> inline T Max(T a,Args... args){
        T b=Max(args...);
        return (a>b)?a:b;
    }
    template<typename T> inline T Min(T a) { return a; }
    template<typename T,typename... Args> inline T Min(T a,Args... args){
        T b=Min(args...);
        return (a<b)?a:b;
    }

    #ifdef LOCAL
        inline char gc() { return getchar(); }
    #else
        inline char gc() {
            static char s[1<<20|1]={0},*p1=s,*p2=s;
            return (p1==p2)&&(p2=(p1=s)+fread(s,1,1<<20,stdin),p1==p2)?EOF:*(p1++);
        }
    #endif
    inline i64 read(){
        register i64 ans=0;register char c=gc();register bool neg=0;
        while(c<48||c>57) neg^=!(c^'-'),c=gc();
        while(c>=48&&c<=57) ans=(ans<<3)+(ans<<1)+(c^48),c=gc();
        return neg?-ans:ans;
    }

    char Output_Ans[1<<20|1],*Output_Cur=Output_Ans;
    inline void output() { Output_Cur-=fwrite(Output_Ans,1,Output_Cur-Output_Ans,stdout); }
    inline void print(char c){
        if(Output_Cur-Output_Ans+1>>20) output();
        *(Output_Cur++)=c;
    }
    inline void print(char *s) { while(*s) print( *(s++) ); }
    inline void print(u64 x){
        if(!x) { print('0'); return ; }
        char buf[30]={0},*p=buf+28;
        while(x) *(p--)=x%10+48,x/=10;
        print(p+1);
    }
    inline void print(u32 x) { print( (u64)x ); }
    inline void print(i64 x){
        if(x<0) print('-'),x=-x;
        print( (u64)x );
    }
    inline void print(i32 x){
        if(x<0) print('-'),x=-x;
        print( (u64)x );
    }
}
using namespace HABIT;

inline i64 sum(i64 n) { return n*(n+1)/2; }

inline i64 ans(i64 n){
    return sum(n)-3*sum(n/3)-5*sum(n/5)+15*sum(n/15);
}

int main(){
    print( ans(read()) );
    output();
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
signed main() {
    int dp[(1<<12)+5];
    fill(dp,dp+(1<<12)+5,INF);
    int n,m;cin>>n>>m;
    int A[m],B[m];
    rep(i,m){
        int a,b;cin>>a>>b;
        int s=0;
        A[i]=a;
        rep(i,b){
            int x;cin>>x;
            x--;
            s+=(1<<x);
        }
        B[i]=s;
        
    }
    dp[0]=0;
    rep(i,m){
        rep(j,1<<n){
            dp[B[i]|j]=min(dp[B[i]|j],dp[j]+A[i]);
        }    
    }
    if(dp[(1<<n)-1]==INF)cout<<-1<<endl;
    else cout<<dp[(1<<n)-1]<<endl;
    
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

int64_t mabs(int64_t x) {
    return x < 0 ? -x: x;
}

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int64_t x, y;
    cin >> x >> y;

    if (x == y) {
        cout << "0\n";
    } else {
        int64_t ans = 0;
        if (mabs(mabs(x + 1) - mabs(y)) > mabs(mabs(x) - mabs(y))) {
            x *= -1;
            ans++;
        }
        ans += mabs(mabs(x) - mabs(y));
        x += mabs(mabs(x) - mabs(y));
        if (x != y) {
            ans++;
        }
        cout << ans << "\n";
    }
}

Measured memory_bytes: 256