akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <set>
#include <fstream>
#include <cstring>
#include <climits>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

#define ll long long
#define mod 1000000007

ll a[3001];
ll dp[3001][3001];

ll solve(int l, int r) {

	if (l > r)
		return INT_MIN;
	if (l == r)
		return a[l];
	if (l == r - 1)
		return max(a[l], a[r]);

	if (dp[l][r] == -1)
		dp[l][r] = max(a[l] + min(solve(l + 2, r), solve(l + 1, r - 1)), a[r] + min(solve(l + 1, r - 1), solve(l, r - 2)));

	return dp[l][r];
}

int main() {

	int n;
	cin >> n;
	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	memset(dp, -1, sizeof(dp));
	cout << 2 * solve(0, n - 1) - sum;
	return 0;
}

Measured memory_bytes: 70784
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    a1 = 0
    for i in range(n):
        if i % 2 == 0:
            a1 += a[i]
        else:
            a1 -= a[i]
    ans = []
    ans.append(a1)
    for i in range(n-1):
        ansl = ans[-1]
        ans.append(a[i]*2-ansl)
    print(" ".join(map(str, ans)))
resolve()

Measured memory_bytes: 84324
s=list(input())

k=int(input())

ans = []

for alf in s:
    if alf == 'a':
        ans.append('a')
    else:
        if 123 - ord(alf) <= k:
            k -= 123 - ord(alf)
            ans.append('a')
        else:
            ans.append(alf)
if 0 < k:
    amari = (ord(ans[-1])-97+k)%26
    ans[-1] = chr(amari+97)
    
print(''.join(map(str,ans)))

Measured memory_bytes: 85220
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long

using namespace std;
using P = pair<int,int>;

int main(){

  int N, a;
  cin >> N;
  int ans = 0;
  vector<int> vec(N);

  for (int i = 0; i < N; i++){
    cin >> a;
    vec.at(i) = a;
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());

  bool flag = true;
  int check = 0;
  int cnt = 0;

  while (flag == true){
    if(flag == false) break;

    bool first = true;
    for (int i = 0; i < N; i++) {
      if(vec.at(i)%2 != 0){
        vec.at(i) = vec.at(i)*3;
      } else {
        if(first == true){
          vec.at(i) = vec.at(i)/2;
          first = false;
        } else {
          vec.at(i) = vec.at(i)*3;
        }
      }
    }
    if(first == true) break;
    ans++;
  }

  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 3648
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        k: usize,
        n: usize,
        a: [usize; n]
    };

    let mut distance: usize = 0;
    let mut index = 0;
    let mut sum_distance = 0;

    for i in 0..n {
        if i == 0 {
            let distance_back = a[i] + k - a.last().unwrap();

            if distance_back > distance {
                distance = distance_back;
                index = i;
            }
        } else {
            let distance_back = a[i] - a[i - 1];

            if distance_back > distance {
                distance = distance_back;
                index = i;
            }
        }
    }

    sum_distance = if index == 0 {
        k - (a[0]) - (k - a.last().unwrap())
    } else {
        k - (a[index] - a[index - 1])
    };

    println!("{}", sum_distance);
}


Measured memory_bytes: 4928
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 1e6+100;

long long A,B,k,ans,res;

int main()
{
	cin>>k>>A>>B;
	ans = k+1;
	if(B<=A){
		cout<<ans<<endl;
		return 0;
	}
	k = k-(A-1);
	if(k<=0){
		cout<<ans<<endl;
		return 0;
	}
	long long sum = k/2;
	res=A;
	res += sum*(B-A);
	if(k&1) res++;
	cout<<max(res,ans)<<endl;
	return 0;
}
/*
7 3 4
 */

Measured memory_bytes: 256
N, A, B = map(int,input().split())
X = input()
S = A+B

cnt1 = 0
cnt2 = 0

for i in range(len(X)):
	if X[i] == "c":
		print("No")

	elif X[i] == "a":
		if cnt1 < S:
			print("Yes")
			cnt1 += 1
		else: print("No")
	else:
		if cnt1 < S and cnt2 < B:
			print("Yes")
			cnt1 += 1
			cnt2 += 1
		else: print("No")



Measured memory_bytes: 4016
#include "bits/stdc++.h"
using namespace std;

int main() {
    int n;
    long long res = 0;
    cin >> n;
    vector< int> v(5);
    while (n--) {
        string z; cin >> z;
        if (z[0] == 'M') v[0]++;
        if (z[0] == 'A') v[1]++;
        if (z[0] == 'R') v[2]++;
        if (z[0] == 'C') v[3]++;
        if (z[0] == 'H') v[4]++;
    }

    for (int i = 0; i < 5; ++i)
        for (int j = i + 1; j < 5; ++j)
            for (int k = j + 1; k < 5; ++k) {
                res += 1LL * v[i] * v[j] * v[k];
            }

    cout << res << endl;
}

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


int main() {
  string s , t ;
  cin >> s >> t ;
  
  bool ans = false ;
  
  for(int i = 0 ; i < s.size() ; i++ ){
    if(s==t){
      ans = true ;
      break;
    }
    s= s.back()+ s.substr(0,s.size()-1);
  }
  
  if(ans==true){
    cout <<"Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
  
  

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
//#define DEBUG
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int main(void) {
#ifdef DEBUG
	printf("");
#endif

	char N[4] = { '\0' };
	scanf("%s", &N);
#ifdef DEBUG
	printf("%d\n",strlen(N));
#endif

	int flag = 0;
	int i;
	for (i = 0; i < (strlen(N)+1)/2; i++) {
		if (N[i] != N[strlen(N)-1-i]) {
#ifdef DEBUG
			printf("%c %c\n",N[i], N[strlen(N) -1 - i]);
#endif
			flag = 1;
			break;
		}
	}

	if (flag) {
		printf("No\n");
	}
	else {
		printf("Yes\n");
	}
}


Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int[] l = new int[n];
    public static void main(String[] args){
        for (int i=0; i<n; i++) l[i] = sc.nextInt();
        Arrays.sort(l);
        int ans = 0;
        for (int i=0; i<n-1; i++){
            for (int j=i+1; j<n; j++){
                int lower = j;
                int upper = n;
                while (upper-lower > 1){
                    int mid = (lower+upper)/2;
                    if (l[mid]<l[i]+l[j]){
                        lower = mid;
                    }else {
                        upper = mid;
                    }
                }
                ans += (lower-j);
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 26640
#define TEST_MODE true

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (a)-1; i >= (int)b; --i)
#define range(i, a, b, c) for (int i = a;             \
                               c > 0 ? i < b : i > b; \
                               i += c)
#define chmax(a, b) (a = (a) < (b) ? (b) : (a))
#define chmin(a, b) (a = (a) > (b) ? (b) : (a))
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define ifnot(a) if (not(a))
#define int long long

#ifdef LOCAL_ENV

#if TEST_MODE == true
const bool test = true;
#define dump(x) cerr << #x << " = " << (x) << " "
#else
const bool test = false;
#define dump(x) 
#endif

#else
const bool test = false;
#define dump(x) 
#endif

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
const int INF = (int)1 << 60;
const ll INFL = (ll)1 << 60;
ll mod_n = (int)1e9 + 7;
const double eps = 1e-10;
typedef long double Real;
// return -1, 0, 1
int sgn(const Real &r) { return (r > eps) - (r < -eps); }
int sgn(const Real &a, const Real &b) { return sgn(a - b); }

//.....................
const int MAX = (int)2e5 + 5;

vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while (getline(ss, buffer, sep))
    {
        v.push_back(buffer);
    }
    return v;
}

template <class InputIterator>
int sum(InputIterator begin, InputIterator end)
{
    return accumulate(begin, end, 0ll);
}

template<typename T>
T gcd(T a, T b)
{
	T c;
	while (a != 0) {
		c = a; a = b%a;  b = c;
	}
	return b;
}

void solve();

class Solver {
public: 
    string s;

    int N;

    void solve() {
        cin >> N;
        rep2(h, 1, 3600) rep2(n, 1, 3600) {
            int a = 4 * h * n - n * N - h * N;
            int b = h * n * N;
            if (a <= 0) continue;
            if (b % a != 0) continue;
            cout << h << " " << n << " " << b / a << endl;
            return;
        }
    }
};

signed main()
{
    srand(time(NULL));
    cout << fixed << setprecision(20);
    auto ptr = new Solver();
    ptr->solve();
    delete ptr;
    // while (true) {    
    //     auto ptr = new Solver();
    //     ptr->solve();
    //     delete ptr;
    // }
    return 0;
}

// class Mycin {
// 	bool flag = true;
// public:
// 	Mycin& operator >> (int& a) {flag = scanf("%lld", &a) != EOF; return *this;}
// 	Mycin& operator >> (char& a) {flag = scanf("%c", &a) != EOF; return *this;}
// 	Mycin& operator >> (string& s) {flag = (bool)(cin >> s); return *this;}
// 	operator bool() {return flag;}
// } mycin;
 
// class Mycout {
// public:
// 	Mycout& operator << (const int& a) {printf("%lld", a); return *this;}
// 	Mycout& operator << (const char c) {printf("%c", c); return *this;}
// 	Mycout& operator << (const string& s) {printf("%s", s.c_str()); return *this;}
// } mycout;
 
// #define cin mycin
// #define cout mycout
// #define endl '\n'

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

# define mp make_pair
# define pb push_back
# define PI acos(-1)
# define ff first 
# define ss second 
# define endl '\n'
# define vt vector
# define all(c) (c).begin(), (c).end()
# define rep(i,a,b) for(int i = a ; i < b ; ++i)

typedef long long ll ; 
typedef long double ld ; 
typedef pair<int,int> pii ; 
typedef pair<ll,ll> pll ;

template<class T> bool umin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int MOD = 1e9+9 ;
const ll inf = 1e18 ;  
const ll mod = 1e9+7 ;  

ll nCr(ll n,ll r){ll t=1;if(r>n)return 0;if(r>n-r)r=n-r;for(ll i=0;i<r;i++){t*=(n-i);t/=(i+1);}return t;}
ll power(ll a, ll n) { ll r=1;while(n){if(n&1)r=(r*a)%MOD;n>>=1;a=(a*a)%MOD;}return r%MOD;}



vt<pii> dir =  {{-1,0} , {1, 0} , {0,-1} , {0,1}} ; 

// ==========Start Here==============

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; 
 	int n , m ; 
 	cin >> n >> m ; 
 	map<int,int> pr ; 
 	vt<bool> vis(n+1) ; 
 	int r ; 
 	string t ;
 	rep(i,0,m) {
 		cin >> r >> t ; 
 
 		if(!vis[r]) {
 			if(t == "WA")
 				pr[r]++;
 			else 
 				vis[r] = 1 ; 
 		}
 	}
 	int ac = 0 , pe = 0 ;
 	rep(i,1,n+1) {
 		if(vis[i] == 1) {
 			ac++;
 			pe += pr[i] ; 
 		}

 	}
 	cout << ac << " " << pe << endl ; 
	return 0 ; 
}

Measured memory_bytes: 8252
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int a[10000]={0};
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	sort(a,a+n);
	long long num=0;
	for(int i=0;i<n-2;i++)
	{
		for(int j=i+1;j<n-1;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if(a[k]<(a[i]+a[j])&&a[i]<(a[j]+a[k])&&a[j]<(a[k]+a[i]))
				num++;
			}
		}
	}
	printf("%lld\n",num);
}

Measured memory_bytes: 256
import static java.lang.System.*;
import java.util.*;

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

        char[] s = sc.next().toCharArray();	
		
		int bc = 0, wc = 0;
		for(int i=0; i<s.length; i++) {
			if(i%2==0&&s[i]=='1' || i%2==1&&s[i]=='0') bc++;
			if(i%2==0&&s[i]=='0' || i%2==1&&s[i]=='1') wc++;
		}

        out.println(Math.min(bc, wc));
    }
}


Measured memory_bytes: 23820
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define mod 1000000007
#define ll long long
#define N 2005
#define K 205
#define pb push_back
struct edge{
    int nxt, u, v;
}e[N << 1];
int dis[N][N], n, u, v, k, head[N], tot, ans;
inline void addedge (int u, int v)
{
    e[++tot] = (edge) {head[u], u, v};
    head[u] = tot;
}
inline void dfs (int *dis, int dep, int u, int fa)
{
    dis[u] = dep;
    edge (i, u)
    {
        if (v == fa) continue;
        dfs(dis, dep + 1, v, u);
    }
}
int main ()
{
    scanf("%d %d", &n, &k);
    fo (i, 2, n)
    {
        scanf("%d %d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    fo (i, 1, n) dfs(dis[i], 0, i, 0);
    if (k & 1)
    {
        k /= 2;
        ans = mod;
        for (int i = 1; i <= tot; i += 2)
        {
            int sum = 0, u = e[i].u, v = e[i].v;
            fo (j, 1, n)
                if (std::min(dis[u][j], dis[v][j]) > k)
                    ++sum;
            ans = std::min(ans, sum);
        }
    }
    else
    {
        k /= 2;
        ans = mod;
        fo (i, 1, n)
        {
            int sum = 0;
            fo (j, 1, n)
                if (dis[i][j] > k)
                    ++sum;
            ans = std::min(ans, sum);
        }
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 16000
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a,b;
int main()
{
	scanf("%d %d",&a,&b);
	if(a+b==15)
		printf("+\n");
	else if(a*b==15)
		printf("*\n");
	else
		printf("x\n");
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define fo(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
#define rd read()
#define maxn 500001
#define gc getchar()
#define mem(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define pb push_back
#define db double
#define pu puts(" ")
using namespace std;

int read()
{
	int x=0,f=1;
	char ch=gc;
	while(!isdigit(ch))
	{
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(isdigit(ch))x=x*10+ch-48,ch=gc;
	return x*f;
}
void print(char x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+48);
}
int qp(int a,int b,int mod)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=(ll)ans*a%mod;
		a=(ll)a*a%mod;
		b>>=1;
	}
	return ans;
}
int ans;
int main()
{
    int k=rd;
    fo(i,1,k)fo(j,1,k)
    {int n=__gcd(i,j);
    fo(l,1,k)ans+=__gcd(n,l);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstring>

typedef long long ll;

using namespace std;

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

    int memo[n];

    for(int i = 0;i < n; i++){
        memo[i] = 1e9+5;
    }
    memo[0] = 0;
    // memo[1] = abs(jumps[0]-jumps[1]);

    for(int i = 1; i < n; i++){
        // memo[i] = abs(jumps[i]-jumps)
        for(int j = 1; j <= k; j++){
            if(i-j >= 0){
                memo[i] = min(abs(jumps[i]-jumps[i-j])+memo[i-j], memo[i]);
            }
        }
    }



    // for(auto itr: memo){
    //     cout << itr<<" ";
    // } cout << endl;

    cout << memo[n-1];
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
//Optimisations
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("O2")
//shortcuts for functions
#define pb push_back
#define mp make_pair
#define ff first 
#define ss second
#define all(v) v.begin(),v.end()
#define prec(n) fixed<<setprecision(n)
#define n_l '\n'
// make it python 
#define gcd __gcd
#define append push_back
#define str to_string
// utility functions shortcuts
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sswap(a,b) {a=a^b;b=a^b;a=a^b;}
#define swap(a,b) {auto temp=a; a=b; b=temp;}
#define init(dp) memset(dp,-1,sizeof(dp));
#define set0(dp) memset(dp,0,sizeof(dp));
#define bits(x) __builtin_popcount(x)
#define SORT(v) sort(all(v))
#define endl "\n"
#define forr(i,n) for(ll i=0;i<n;i++)
// declaration shortcuts
typedef long long int ll;
#define int ll
// Constants
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr ll INF = 1999999999999999997; 
constexpr int inf= INT_MAX;
constexpr int MAXSIZE = int(1e6)+5;
constexpr auto PI  = 3.14159265358979323846L;
constexpr auto oo  = numeric_limits<int>::max() / 2 - 2;
constexpr auto eps = 1e-6;
constexpr auto mod = 1000000007;
constexpr auto MOD = 1000000007;
constexpr auto MOD9 = 1000000009;
constexpr auto maxn = 100006;
//void IOfile(){
//freopen(file_name, reade_mode, stdin);
//freopen(file_name, write_mode, stdout);
//}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int32_t main(){
	fastio();
	int n;
	cin>>n;
	set<string>s;
	for(int i=0;i<n;i++){
		string x;
		cin>>x;
		s.insert(x);
	}
	cout<<s.size()<<"\n";
}

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

ll N;
vector<ll> A;

int main(void){
    
    cin >> N;
    for(ll i = 1; i <= N; ++i){
        ll n;
        cin >> n;
        A.push_back(n - i);
    }
    sort(A.begin(), A.end());
    
    ll ans = LONG_MAX, C = N / 2;
    for(ll c = C - 1; c < C + 1; ++c){
        ll sum = 0;
        for(ll i = 0; i < N; ++i) sum += abs(A[i] - A[c]);
        ans = min(ans, sum);
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int a[200020];
int co[200020] = { 0 };
vector<int> ans;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = n; i > 0; i--) {
		if (a[i] % 2 != co[i] % 2) {
			ans.push_back(i);
			for (int j = 1; j * j <= i; j++) {
				if ((i) % j == 0) {
					co[j]++;
					if (j != i / j) {
						co[i / j]++;
					}
				}
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i];
		if (i != ans.size() - 1) {
			cout << " ";
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3064
let ch v = if v = "25" then "Christmas" else v;;
let ch2 v = if v = "24" then "Christmas Eve" else v;;
let ch3 v = if v = "23" then "Christmas Eve Eve" else v;;
let ch4 v = if v = "22" then "Christmas Eve Eve Eve" else v;;



 print_string (ch4(ch3(ch2(ch(read_line ()))))); print_string "\n";;

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main() {

  uint8_t *sa = (uint8_t *)calloc(100, sizeof(uint8_t)), *sb = (uint8_t *)calloc(100, sizeof(uint8_t)), *sc = (uint8_t *)calloc(100, sizeof(uint8_t));
  scanf("%s\n%s\n%s", sa, sb, sc);

  uint8_t card = sa[0];
  uint8_t winner;
  sa++;
  while(card) {
    switch(card) {
    case 'a':
      card = sa[0];
      sa++;
      winner = 'A';
      break;
    case 'b':
      card = sb[0];
      sb++;
      winner = 'B';
      break;
    case 'c':
      card = sc[0];
      sc++;
      winner = 'C';
      break;
    }
  }

  printf("%c\n", winner);
  
  return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;

class ModInt{
public:
    ModInt(){
        x = 0;
    }
    ModInt(int v){
        x = (((v % mod) + mod) % mod);
    }
    ModInt(long long v){
        x = (((v % mod) + mod) % mod);
    }
    ModInt(unsigned long long v){
        x = (((v % mod) + mod) % mod);
    }

    ModInt operator-() const {return ModInt(-x);}
    ModInt& operator+=(const ModInt& a){
        x = (x + a.x) % mod;
        return *this;
    }
    ModInt& operator-=(const ModInt& a){
        x = (x + mod - a.x) % mod;
        return *this;
    }
    ModInt& operator*=(const ModInt& a){
        x = (x * a.x) % mod;
        return *this;
    }
    ModInt operator+(const ModInt& a) const{
        ModInt res(*this);
        res += a;
        return res;
    }
    ModInt operator-(const ModInt& a) const{
        ModInt res(*this);
        res -= a;
        return res;
    }
    ModInt operator*(const ModInt& a) const{
        ModInt res(*this);
        res *= a;
        return res;
    }
    ModInt power(long long a) const{
        if(a == 0) return 1;
        auto b = power(a >> 1);
        b *= b;
        if(a & 1) b *= *this;
        return b;
    }
    ModInt inverse() const{
        return power(mod - 2);
    }
    ModInt& operator/=(const ModInt& a){
        (*this) *= a.inverse();
        return *this;
    }
    ModInt operator/(const ModInt& a)const{
        ModInt res(*this);
        res /= a;
        return res;
    }
    friend ostream& operator<<(ostream& os, const ModInt& a){
        os << a.x;
        return os;
    }

    static ModInt add(long long a, long long b){
        ModInt res(a);
        res += b;
        return res;
    }

    static long long get_mod(){ return mod;}

private:
    static const long long mod = 1000000007;
    long long x;
};

int main()
{
    int N;
    cin >> N;
    vector<int> counts(64, 0);
    vector<ull> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
        for(int j=0; j<64; j++){
            if(A[i] & ((ull)1 << j)) counts[j]++;
        }
    }
    ModInt res(0);
    for(int i=0;i<N;i++){
        for(int j=0; j<64; j++){
            auto b = (ull)1 << j;
            ModInt v(b);
            if(A[i] & b){
                v *= (N - counts[j]);
            }else{
                v *= counts[j];
            }
            res += v;
        }
    }
    res /= 2;
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 2560
count = 0
n = gets.chomp.to_i

cards = gets.split(" ")
suit,nums = cards.map{|x|x[0]},cards.map{|x|x[1].to_i}
cards = suit.zip(nums)
array = Marshal.load(Marshal.dump(cards))

i=0
while i<n
  j = n-1
  while j > i
    if array[j][1] < array[j-1][1]
      array[j],array[j-1] = array[j-1],array[j]
      count = count+1
    end  
    j = j-1
  end
  i=i+1
end

i=0
while i < n 
  printf("%s%d",array[i][0],array[i][1])
  if i+1 != n
  print " "
  end
  i = i+1
end

print "\n"
print "Stable"
print "\n"

array2 = Marshal.load(Marshal.dump(cards))
i = 0
while i<n
  j = i+1
  min = i
  while j<n
    if array2[min][1] > array2[j][1]
      min = j
    end  
    j = j+1
  end
  if min != i
  array2[min],array2[i] = array2[i],array2[min]
  count = count + 1
  end
  i=i+1
end

i=0
while i < n 
  printf("%s%d",array2[i][0],array2[i][1])
  if i+1 != n
  print " "
  end
  i = i+1
end

i,flag = 0,true
while i < n 
  flag = false if array[i][0] != array2[i][0]
  i = i+1
end

print "\n"
printf flag == true ? "Stable":"Not stable"
print "\n"

Measured memory_bytes: 6184
#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int main(){
	scanf("%s",s+1);
	int cnt=0,l=strlen(s+1);
	for(int i=l;i>=1;i--){
		if(s[i]<'5'||(s[i]=='5'&&s[i-1]<'5'))cnt+=s[i]-'0';
		else{
			cnt+=10-(s[i]-'0');
			s[i-1]++;
		}
	}
	if(s[0])cnt++;
	printf("%d\n",cnt);
	return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define MMP(a, b, c) make_pair(make_pair(a, b), c)
#define MAX 1000000000
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define PI 3.14159265359

int main(){
    iostream::sync_with_stdio(false);

    int N,M,C;
    cin >> N >> M >> C;
    long long sumD = 0;
    vector<pair<int,int> > road[100000];
    for(int i=0; i<M; i++){
        int a,b,d;
        cin >> a >> b >> d;
        a--; b--;
        road[a].push_back(MP(b, d));
        road[b].push_back(MP(a, d));
        sumD += d;
    }

    long long cost[100000];
    for(int i=0; i<N; i++) cost[i] = LL_MAX;
    cost[0] = 0;
    priority_queue<pair<long long,int> > que;
    que.push(MP(LL_MAX, 0));
    while(!que.empty()){
        for(int i=0; i<road[que.top().second].size(); i++){
            if(cost[road[que.top().second][i].first] > LL_MAX-que.top().first + road[que.top().second][i].second){
                cost[road[que.top().second][i].first] = LL_MAX-que.top().first + road[que.top().second][i].second;
                que.push(MP(LL_MAX-cost[road[que.top().second][i].first], road[que.top().second][i].first));
            }
        }
        que.pop();
    }

    pair<long long,int> d[100000];
    for(int i=0; i<N; i++) d[i] = MP(cost[i], i);
    sort(d, d+N);

    long long answer = LL_MAX;
    set<int> already;
    for(int i=0; i<N; i++){
        for(int j=0; j<road[d[i].second].size(); j++){
            if(already.count(road[d[i].second][j].first) == 1) sumD -= road[d[i].second][j].second;
        }
        already.insert(d[i].second);
        answer = min(answer, C*d[i].first+sumD);
    }
    cout << answer << endl;
    
    return 0;
}


Measured memory_bytes: 19032
import java.util.Scanner;

public class Main {

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

        final int N = sc.nextInt();

        int n = N;
        int ans = 0;
        for (int i = 0; i <= String.valueOf(N).length(); i++) {
            ans += n % 10;
            n /= 10;
        }

        if (ans == 1 && String.valueOf(N).length() > 1) {
            System.out.println(10);
        } else {
            System.out.println(ans);
        }
    }
}


Measured memory_bytes: 21844
# !/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

OR
input:
4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0

output:
NEGATIVE CYCLE
"""

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source].setdefault(target, cost)
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

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

using namespace std;


int main()
{
	string S;
	string a, b, a1, a2, b1, b2;
	cin >> S;
	int size = (int)S.length();
	a = S.substr(0, size / 2);
	b = S.substr(size / 2 + 1, size - 1);
	auto reva = a;
	auto revb = b;
	//reverse(reva.begin(),reva.end());
	reverse(revb.begin(), revb.end());
	if (reva != revb)
	{
		cout << "No" << endl;
		return 0;
	}

	int size_a = (int)a.length();
	int size_b = (int)b.length();
	a1 = a.substr(0, size_a / 2);
	a2 = a.substr((size_a + 1 )/ 2, size_a - 1);
	b1 = b.substr(0, size_a / 2);
	b2 = b.substr((size_a +1)/ 2 , size_b - 1);

	auto reva1 = a1;
	auto reva2 = a2;
	auto revb1 = b1;
	auto revb2 = b2;
	reverse(reva1.begin(), reva1.end());
	//reverse(reva2.begin(),reva2.end());
	reverse(revb1.begin(), revb1.end());
	//reverse(revb2.begin(),revb2.end());

	if (reva1 == reva2 && revb1 == revb2)
	{
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    is_approved = True
    for num in A:
        if num % 2 == 0:
            if not (num % 3 == 0 or num % 5 == 0):
                is_approved = False
    if is_approved:
        print("APPROVED")
    else:
        print("DENIED")

if __name__ == "__main__":
    solve()

Measured memory_bytes: 9084
l = input().split()
n = int(l[0])
k = int(l[1])
lst = []
for i in range(n):
  lst.append(int(input()))
lst.sort()
min_max = []
for i in range(n-k+1):
  min_max.append(lst[i + k - 1] - lst[i])
print(min(min_max))

Measured memory_bytes: 11288
N , x = map(int,input().split())
ans = 0
L = list(map(int,input().split()))
eat = 0
for i in range(len(L)-1):
    if L[i+1] + L[i] > x:
        if L[i] <= x:
            eat = L[i+1] + L[i] - x
            L[i+1] -= eat 
            ans += eat
        else:
            eat = L[i+1] + L[i] - x
            L[i+1] = 0
            L[i] = x
            ans += eat
print(ans)

Measured memory_bytes: 14052
import java.io.IOException;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int h = scanner.nextInt();
			int w = scanner.nextInt();
			if ((h | w) == 0)
				break;
			StringBuilder b = new StringBuilder();
			for (int i = 0; i < h; i++)
				b.append(scanner.next());
			PriorityQueue<Point> pq = new PriorityQueue<Main.Point>();
			int k = b.indexOf("@");
			int gg = b.indexOf("E");
			gy = gg / w;
			gx = gg % w;
			int md = getMD(k / w, k % w);
			pq.offer(new Point(k / w, k % w, b.toString(), 1, md + 1));
			int ans = -1;
			Set<String> set = new HashSet<String>();
			loop: while (!pq.isEmpty()) {
				Point p = pq.poll();
				String g = p.g;
				int d = p.d;
				int y = p.y;
				int x = p.x;
				int a = y * w + x;
				if (set.contains(g))
					continue;
				set.add(g);
				for (int i = 0; i < 4; i++) {
					int sy = y + dy[i];
					int sx = x + dx[i];
					int aa = sy * w + sx;
					char c = g.charAt(aa);
					if (c == '#' || c == 'w')
						continue;
					if (c == 'E') {
						ans = d;
						break loop;
					}
					if (c == '.') {
						char[] tmp = g.toCharArray();
						tmp[a] = '.';
						tmp[aa] = '@';
						int nmd = getMD(sy, sx);
						pq.offer(new Point(sy, sx, String.valueOf(tmp), d + 1,
								nmd + d + 1));
					}
					if (c == 'c') {
						char[] tmp = g.toCharArray();
						tmp[aa] = '.';
						while (true) {
							int ny = sy + dy[i];
							int nx = sx + dx[i];
							char nc = tmp[ny * w + nx];
							if (nc == '#' || nc == 'c') {
								tmp[sy * w + sx] = 'c';
								break;
							}
							if (nc == 'w') {
								tmp[ny * w + nx] = '.';
								break;
							}
							sy = ny;
							sx = nx;
						}
						pq.offer(new Point(y, x, String.valueOf(tmp), d, p.md));
					}
				}

			}
			System.out.println(ans);
		}
	}

	private int getMD(int i, int j) {
		return Math.abs(i - gy) + Math.abs(j - gx);
	}

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

	class Point implements Comparable<Point> {
		int y, x;
		String g;
		int d, md;

		public Point(int y, int x, String g, int d, int md) {
			super();
			this.y = y;
			this.x = x;
			this.g = g;
			this.d = d;
			this.md = md;
		}

		@Override
		public String toString() {
			return "Point [y=" + y + ", x=" + x + ", g=" + g + ", d=" + d
					+ ", md=" + md + "]";
		}

		@Override
		public int compareTo(Point o) {
			if (md == o.md)
				return o.d - d;
			return md - o.md;
		}

	}
}

Measured memory_bytes: 97504
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647 -> 10桁
// MAX ll 9,223,372,036,854,775,807 -> 19桁
// MAX O(n) 10^8 -> 8回
// double pi = M_PI or acos(-1)
// printf("%.10f\n", ans);

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

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

    while(!isPrime(x)) {
        x++;
    }

    cout << x << endl;

    return 0;
}


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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a[] = new int[3];
		for (int i = 0; i <= 2; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		// a[2]が目標
		int ans = 0;
		ans += a[2] - a[1];
		a[0]=a[0]+a[2] - a[1];
		a[1] = a[2];


		if (a[2] == a[0]) {

		} else {

			if ((a[2]-a[0]) % 2 == 1) {
				ans++;
				a[2]++;
				a[1]++;
			}

			ans=ans+(a[2]-a[0])/2;
		}
System.out.println(ans);
	}
}

Measured memory_bytes: 21588
N, x = [int(n) for n in input().split(" ")]
A = [int(a) for a in input().split(" ")]

cnt = 0
if A[0] > x:
  cnt += A[0] - x
  A[0] = x

for i in range(1, len(A)):
  if A[i] + A[i - 1] > x:
    cnt += A[i] + A[i - 1] - x
    A[i] = x - A[i - 1]

print(cnt)

Measured memory_bytes: 20076
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def sub(al, ar, b):
    tmp = (al + ar) - b
    if tmp < 0:
        return 0, al + ar
    else:
        if al > b:
            return ar, b 
        else:
            return ar+(al-b), b

ans = 0

ext, res = sub(A[0], A[1], B[0])
ans += res
for i in range(1, N):
    ext, res = sub(ext, A[i+1], B[i])
    ans += res

print(ans)

Measured memory_bytes: 19648
# ITP1_10_B
import math

a, b, c = map(float, input().split())
s = a * b * math.sin(math.radians(c)) / 2
l = a + b + math.sqrt(a**2 + b**2 - 2 * a * b * math.cos(math.radians(c)))
h = b * math.sin(math.radians(c))

print(s)
print(l)
print(h)



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

int main()
{
	int N;
	cin >> N;
	bool ok = false;
	for (int i = 1; i <= 9; ++i)
	{
		if (N % i == 0 && N/i >= 1 && N/i <= 9)
		{
			ok = true;	
		}
	}
	if (ok) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define Rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

int main() {
	int N;
	cin >> N;
	vector<ll> A(N);
	Rep(i, N) cin >> A[i];
	sort(A.begin(), A.end());
	For(i, 1, N) {
		if (A[i] == A[i - 1]) {
			A[i] = 0;
			A[i - 1] = 0;
		}
	}
	sort(A.begin(), A.end());
	int n = upper_bound(A.begin(), A.end(), 0) - A.begin();
	cout << N - n << endl;
	return 0;
}

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

using ll = long long;
//print(fixed << setprecision(10));
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define repk(i,n,k) for(ll i = k; i < (n); i++)
#define all(n) n.begin(), n.end()
#define print(n) cout << n << endl
double PI = acos(-1.0);
int INF = 1e9;
ll LINF = 1e18;
ll MOD = 1e9+7;

ll root(ll x, vector<ll> &par){
    if(par[x]==0) return x;
    return root(par[x],par);
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    ll n,m;
    cin >> n >> m;
    vector<ll> par(n+1,0);
    rep(i,m){
        ll a,b;
        cin >> a >> b;
        ll ra = root(a,par);
        ll rb = root(b,par);
        if(ra != rb){
            par[b]=ra;
            par[rb]=ra;
        }
    }
    ll sum=0;
    rep(i,n) if(par[i+1]==0) sum++;
    print(sum-1);
    return 0;
}

Measured memory_bytes: 3996
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
arr = []
nn = 0
kk = 0
lc = 0
while l = $stdin.gets do
  if lc == 0
    tmp = l.chomp.split(" ").map(&:to_i)
    nn = tmp[0]
    kk = tmp[1]
  else
    arr << l.chomp.to_i
  end
  lc += 1
end

arr.sort!

# body
if $debugFlag
  p nn
  p kk
  p arr
end

tmp_min = nil
for i in 0..nn-kk do
  x = (arr[i+kk-1]  - arr[i])
  if tmp_min == nil
    tmp_min = x
  elsif tmp_min > x
    tmp_min = x
  end
end

puts tmp_min

Measured memory_bytes: 4016
n, a = gets.split.map(&:to_i)
ary = gets.split.map{|i| i.to_i - a}

h = Hash.new(0)
h[0] = 1
hh = h.dup

n.times do |i|
    h.each do |e, v|
        hh[ary[i]+e] += v
    end
    h = hh.dup
end

p h[0]-1

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

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
using namespace std;

int main(void)
{
	int N; cin >> N;
	int A, B; cin >> A >> B;

	int ans = 0;
	rep(j, 1, N + 1) {
		int sum = 0;
		int i = j;
		while (i > 0) {
			sum += i % 10;
			i /= 10;
		}
		if (sum >= A && sum <= B)ans += j;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 20;

vector<int> data;
int a[MAX_N];
int h[MAX_N];
int n,K;

template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first1 ,
  BidirectionalIterator last1 ,
  BidirectionalIterator first2 ,
  BidirectionalIterator last2 )
{
  if (( first1 == last1 ) || ( first2 == last2 )) {
    return false ;
  }
  BidirectionalIterator m1 = last1 ;
  BidirectionalIterator m2 = last2 ; --m2;
  while (--m1 != first1 && !(* m1 < *m2 )){
  }
  bool result = (m1 == first1 ) && !(* first1 < *m2 );
  if (! result ) {
    while ( first2 != m2 && !(* m1 < * first2 )) {
      ++ first2 ;
    }
    first1 = m1;
    std :: iter_swap (first1 , first2 );
    ++ first1 ;
    ++ first2 ;
  }
  if (( first1 != last1 ) && ( first2 != last2 )) {
    m1 = last1 ; m2 = first2 ;
    while (( m1 != first1 ) && (m2 != last2 )) {
      std :: iter_swap (--m1 , m2 );
      ++ m2;
    }
    std :: reverse (first1 , m1 );
    std :: reverse (first1 , last1 );
    std :: reverse (m2 , last2 );
    std :: reverse (first2 , last2 );
  }
  return ! result ;
}
 
template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first ,
  BidirectionalIterator middle ,
  BidirectionalIterator last )
{
  return next_combination (first , middle , middle , last );
}

int main()
{
	scanf("%d%d",&n,&K);
	int hmax=0;
	rep(i,n){
		scanf("%d",&a[i]);
		h[i] = hmax+1;
		if(a[i] > hmax){
			hmax = a[i];
		}
		data.push_back(i);
	}
	ll ans = (1LL<<60);
	do{
		int cri=0;
		ll res=0;
		rep(j,K){
			int id = data[j];
			cri = max(cri,h[id]);
			if(a[id] < cri){
				res += cri - a[id];
			}
			cri++;
		}
		ans = min(ans,res);
	}while(next_combination(data.begin(),data.begin()+K,data.end()));
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
 
total = 0
dif = 0
for i in range(1,N):
  if (A[i-1]+dif)-A[i]>0:
    total += (A[i-1]+dif)-A[i]
    dif = (A[i-1]+dif)-A[i]
  else:
    dif = 0
print(total)


Measured memory_bytes: 32152
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::tuple<int, int, int>> es;
    std::vector<std::pair<int, int>> w;
    for (int i = 0; i < m; i++) {
        int p, q, c;
        std::cin >> p >> q >> c;
        --p; --q;
        es.emplace_back(p, q, c);
        w.emplace_back(p, c);
        w.emplace_back(q, c);
    }

    std::sort(w.begin(), w.end());
    w.erase(std::unique(w.begin(), w.end()), w.end());

    auto get = [&](int v, int c) {
        return n + std::lower_bound(w.begin(), w.end(), std::make_pair(v, c)) - w.begin();
    };

    std::vector<std::vector<std::pair<int, int>>> g(w.size() + n);
    for (const auto &e : w) {
        int v = get(e.first, e.second);
        g[e.first].emplace_back(v, 1);
        g[v].emplace_back(e.first, 0);
    }
    for (const auto &e : es) {
        auto p = std::get<0>(e), q = std::get<1>(e), c = std::get<2>(e);
        int pv = get(p, c), qv = get(q, c);
        g[pv].emplace_back(qv, 0);
        g[qv].emplace_back(pv, 0);
    }

    constexpr int inf = std::numeric_limits<int>::max() / 2;
    std::vector<int> dist(g.size(), inf);
    std::deque<int> q { 0 };
    dist[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto to : g[v]) {
            if (dist[to.first] <= dist[v] + to.second) continue;
            dist[to.first] = dist[v] + to.second;
            if (to.second) q.push_back(to.first);
            else q.push_front(to.first);
        }
    }

    std::cout << (dist[n - 1] == inf ? -1 : dist[n - 1]) << std::endl;

    return 0;
}


Measured memory_bytes: 38784
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

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

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

int gcd(int a, int b) {
  if (a < b) { swap(a, b); }
  if (b == 0) { return a; }
  return gcd(b, a % b);
}

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

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

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll powmod(ll x, ll y) {
  ll r = 1;
  while (y) {
    if (y & 1) {
      r = r * x % MOD;
    }
    x = x * x % MOD;
    y >>= 1;
  }
  return r;
}

ll fac[200010], facinv[200010];  // 200010 is Larger than 1e5 + 1e5.
void cominit() {
  fac[0] = facinv[0] = 1;
  ll c = 1;
  for (int i = 1; i < 200010; ++i) {
    c = c * i % MOD;
    fac[i] = c;
    facinv[i] = powmod(c, MOD-2);
  }
}

ll combination(ll n, ll k) {
  return (fac[n] * facinv[k] % MOD) * facinv[n-k] % MOD;
}

ll permutation(ll n, ll k) {
  return (fac[n] * facinv[k] % MOD);
}

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

  map<int, int> factors;
  for (int i = 2; i * i <= M; ++i) {
    while (M % i == 0) {
      ++factors[i];
      M /= i;
    }
  }
  if (M > 1) {
    ++factors[M];
  }

  cominit();
  ll r = 1;
  for (auto x : factors) {
    r *= combination(x.second + N - 1, N - 1);
    r %= MOD;
  }

  cout << r << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	string S;
	cin >> S;

	rep(i, S.size() - 1) {
		if (S[i] == 'A' && S[i + 1] == 'C') {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define lli long long int
#define llu unsigned long long int
#define pb push_back
#define rt return 0
#define endln "\n"
#define all(x) x.begin(), x.end()
#define sz(x) (lli)(x.size())
const lli MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
// cout << fixed << setprecision(0) << pi <<endl;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// for multiset
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

void solve() {
    lli x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    lli val = x / d;
    if (k <= val) {
        lli ans = abs(x - k * d);
        cout << ans << endl;
    } else {
        x -= val * d;
        k -= val;
        lli no1 = x;
        lli no2 = abs(x - d);

        if (no1 <= no2) {
            if (k % 2 == 0) {
                cout << no1 << endl;
            } else {
                cout << no2 << endl;
            }
        } else {
            k--;
            if (k % 2 == 0) {
                cout << no2 << endl;
            } else {
                cout << no1 << endl;
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // lli t; cin >> t; while(t--)
    solve();
    rt;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <bitset>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <functional>

using namespace std ;

const int eps=1e-6 ;
const int inf=0x3f3f3f3f ;

#define mp make_pair
#define pb push_back
#define first fi
#define second se
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REP(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)

typedef unsigned long long ull ;
typedef long long ll ;

inline int read(){
	char c ;
	int f=1 ;
	while((c=getchar())<'0' || c>'9') if (c=='-') f=-1 ;
	int res=c-'0' ;
	while((c=getchar())>='0' && c<='9') res=res*10+c-'0' ;
	return res*f ;
}

const int N = 110 ; 

int n,m ;
int a[110],b[110],dp[110][110][330] ;

int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]=read(),b[i]=read() ;
	for (int i=1;i<=n;i++)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=3*j;k++){
		dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]) ;
		dp[i+1][j+1][k+a[i]-a[1]]=max(dp[i+1][j+1][k+a[i]-a[1]],dp[i][j][k]+b[i]) ;
	}
	
	int ans=0 ;
	for (int i=0;i<=n;i++)
	for (int j=0;j<=3*i;j++){
		ll W= (ll) a[1]*i+j;
		if (W<=m) ans=max(ans,dp[n+1][i][j]) ;
	}
	printf("%d",ans) ;
	return 0 ;
}



Measured memory_bytes: 12800
#include<stdio.h>

int main(void) {
	int n = 0;
	int l[100] = { 0 };
	int cnt = 0;
	int i, j, k;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
		scanf("%d", &l[i]);

	for (i = 0; i < n; i++) {				//�z��̏���1��
		for (j = i + 1; j < n; j++) {		//�z��̏���2��
			for (k = j + 1; k < n; k++) {	//�z��̏���3��
				if ((l[i] != l[j]) && (l[j] != l[k]) && (l[k] != l[i])) { //3�̕ӂ��قȂ�Ƃ�������
					if ((l[i] + l[j] > l[k]) && (l[j] + l[k] > l[i]) && (l[k] + l[i] > l[j])) //2�̕ӂ𑫂������̂��c��̕ӂ����傫��
						cnt++; //�����𖞂�������J�E���g�𑝂₵�Ă���
				}
			}
		}
	}
	printf("%d", cnt);
	return 0;
}

Measured memory_bytes: 1736
N, M = map(int, input().split())
MOD = 10**9 + 7

X = list(map(int, input().split()))
Y = list(map(int, input().split()))

sumX = 0
sumY = 0

for i, x in enumerate(X):
    sumX += -(N - (i + 1)) * x + i * x
    sumX %= MOD

for i, y in enumerate(Y):
    sumY += -(M - (i + 1)) * y + i * y
    sumX %= MOD

ans = sumX * sumY % MOD
print(ans)



Measured memory_bytes: 18576