akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
	string s;
	cin >> s;
	string NO = "No";
	string YES = "Yes";
	if(s.size() < 4) {
		cout << NO << endl;			
		return 0;
	}
	if(s.substr(0,4) == "YAKI")
		cout << YES << endl;
	else cout << NO << endl;
	
	return 0;
}

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

template<Int Mod = 1000000007> class modint{
public:
	Int val;
	constexpr modint(const Int x = 0) : val(x % Mod) {if(val < 0) val += Mod;}
	constexpr modint operator+(const modint rhs) const {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const {
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const {
		return modint(*this) /= rhs;
	}
	constexpr modint operator-() const {
		return modint(Mod - val);
	}
	constexpr modint &operator+=(const modint rhs){
		val += rhs.val;
		if(val >= Mod) val -= Mod;
		return *this;
	}
	constexpr modint &operator-=(const modint rhs){
		if(val < rhs.val) val += Mod;
		val -= rhs.val;
		return *this;
	}
	constexpr modint &operator*=(const modint rhs){
		val *= rhs.val;
		val %= Mod;
		return *this;
	}
	constexpr modint &operator/=(const modint rhs){
		return *this *= inv(rhs);
	}
	constexpr modint &operator++(){
		++val;
		if(val == Mod) val = 0;
		return *this;
	}
	constexpr modint &operator--(){
		--val;
		if(val == -1) val = Mod - 1;
		return *this;
	}
	constexpr modint operator<<(const Int rhs) const {
		return modint(*this) << rhs;
	}
	constexpr modint operator>>(const Int rhs) const {
		return modint(*this) >> rhs;
	}
	constexpr modint &operator<<=(const Int rhs){
		val <<= rhs;
		val %= Mod;
		return *this;
	}
	constexpr modint &operator>>=(const Int rhs){
		val >>= rhs;
		val %= Mod;
		return *this;
	}
	constexpr bool operator==(const modint rhs) const {
		return val == rhs.val;
	}
	constexpr bool operator!=(const modint rhs) const {
		return val != rhs.val;
	}
	constexpr bool operator<(const modint rhs) const {
		return val < rhs.val;
	}
	constexpr bool operator>(const modint rhs) const {
		return val > rhs.val;
	}
	constexpr bool operator<=(const modint rhs) const {
		return val <= rhs.val;
	}
	constexpr bool operator>=(const modint rhs) const {
		return val >= rhs.val;
	}
	friend ostream& operator<<(ostream& os, const modint<Mod>& m){
		return os << m.val;
	}
	friend istream& operator>>(istream& is, modint<Mod>& m){
		return is >> m.val;
	}
	static constexpr modint inv(modint m){
		Int a = m.val, b = Mod, u = 1, v = 0;
		while(b){
			Int t = a / b;
			a -= t * b;
			swap(a, b);
			u -= t * v;
			swap(u, v);
		}
		u %= Mod;
		if(u < 0) u += Mod;
		return modint(u);
	}
	constexpr operator Int() const {
		return val;
	}
};
using mint = modint<>;
vector<mint> fact(1, 1);
mint comb(Int n, Int r){
	if(n < 0 || r < 0 || n - r < 0) return 0;
	while(Int(fact.size()) <= n)
		fact.push_back(fact.back() * mint(fact.size()));
	return fact[n] / fact[r] / fact[n-r];
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int n, k; cin >> n >> k;
	using mint = modint<>;
	for(Int i=1; i<=k; ++i){
		mint ans = comb(n-k+1, i) * comb(k-1, i-1);
		cout << ans << "\n";
	}
}

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

int main()
{
	int a[10],k,i,j;
	
	for(i=0;i<5;i++){
		cin>>a[i];
	}
	cin>>k;
	
	for(i=0;i<5;i++){
		for(j=i+1;j<5;j++){
			if(a[j]-a[i]>k){
				cout<<":("<<endl;
				return 0;
			}
		}
	}
	cout<<"Yay!"<<endl;
	
	return 0;
}

Measured memory_bytes: 256
using System;

namespace ConsoleApp3
{
	class Program
	{
		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			var positions = new Position[n];
			for (int i = 0; i < n; i++)
			{
				var p = Console.ReadLine().Split();
				positions[i].xPos = int.Parse(p[0]);
				positions[i].yPos = int.Parse(p[1]);
			}

			double total = 0;
			for (int i = 0; i < n; i++)
			{
				for (int j = i + 1; j < n; j++)
				{
					total += Math.Sqrt(Math.Pow((positions[i].xPos - positions[j].xPos), 2) + Math.Pow((positions[i].yPos - positions[j].yPos), 2));
				}
			}
			Console.WriteLine(total * 2 / n);
		}

		struct Position
		{
			public int xPos;
			public int yPos;
		}
	}
}


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

int selectionSort(int a[], int n){
    int count = 0;
    for (int i = 0; i < n; i++){
        int minj = i;
        for (int j = i; j < n; j++)
            if (a[j] < a[minj]){
                minj = j;
            }
        if (minj != i){
            swap(a[i],a[minj]);
            count++;
        }
    }
    return count;
}

int main(){
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int count = selectionSort(a,n);
    for(int i = 0; i<n; i++){
        if(i>0) cout<<' ';
        cout << a[i];
    }
    cout << endl;
    cout << count << endl;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  
#include <numeric>
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define endl '\n'
using ll = long long;
 
const int precision = 3;
const int modulo =  1000000007; // 10^9 + 7
const ll lmodulo =  1000000007; // 10^9 + 7
 
const double EPS = 1e-9;
const ll inf = 1e18;

// void solve () {
// 	int n; cin >> n;
// 	vector<vector<int>> days(n, vector<int>(3));
// 	for (auto &it : days) {
// 		cin >> it[0] >> it[1] >> it[2];
// 	}

// 	vector<vector<int>> dp(n, vector<int>(3));
// 	dp[0] = days[0];

// 	for (auto i = 1; i < n; ++i) {
// 		dp[i][0] = days[i][0] + max(dp[i - 1][1], dp[i - 1][2]);
// 		dp[i][1] = days[i][1] + max(dp[i - 1][0], dp[i - 1][2]);
// 		dp[i][2] = days[i][2] + max(dp[i - 1][0], dp[i - 1][1]);
// 	}

// 	int ret = max(dp[n - 1][0], dp[n - 1][1]);
// 	ret = max(ret, dp[n - 1][2]);
// 	cout << ret << endl;
// }

void solve () {
	int n; cin >> n;
	vector<int> days(3);
	vector<vector<int>> dp(2, vector<int>(3));

	for (auto &it : dp[0]) cin >> it;

	for (auto i = 1; i < n; ++i) {
		auto cur = i % 2;
		auto prev = (i - 1) % 2;

		cin >> days[0] >> days[1] >> days[2];
		dp[cur][0] = days[0] + max(dp[prev][1], dp[prev][2]);
		dp[cur][1] = days[1] + max(dp[prev][0], dp[prev][2]);
		dp[cur][2] = days[2] + max(dp[prev][0], dp[prev][1]);
	}

	int ind = (n - 1) % 2;
	int ret = max(dp[ind][0], dp[ind][1]);
	ret = max(ret, dp[ind][2]);
	cout << ret << endl;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(precision);
  cout.setf(ios_base::fixed);
  solve();
  return 0;
}



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

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define T(a, b, c) make_pair(a, make_pair(b, c))
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int a[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
	}
	int ans = 0;
	for(int i = 2; i < n; i ++)
	{
		vi v;
		v.pb(a[i -1]);
		v.pb(a[i]);
		v.pb(a[i+1]);
		sort all(v);
		ans += (v[1] == a[i]);
	}
	cout << ans;





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int ns,nl,cnt;
int vec[12][12];
bool used[12][12];
vector<int> dis;
const int INF = 1<<30;

void permutation(int s,int cost,vector<int> P){
  bool fin = true;
  
  for(int i=1;i<=ns;i++){
    if(!used[s][i] && vec[s][i] != INF && i!=s){
      fin = false;
      P.push_back(i);
      used[s][i] = used[i][s] = true;
      permutation(i,cost+vec[s][i],P);
      used[s][i] = used[i][s] = false;
      P.pop_back();
    }
  }
  
  if(fin){
    if(cnt <= cost){
      if(cnt == cost){
	bool AorB = false;//true -> dis, false -> P
	for(int i=0;i<min(dis.size(),P.size());i++){
	  if(dis[i] > P[i]){
	    AorB = false;
	    break;
	  }
	  else if(dis[i] < P[i]){
	    AorB = true;
	    break;
	  }
	}
	if(!AorB){
	  dis.clear();
	  copy(P.begin(),P.end(),back_inserter(dis));
	}
      }
      else if(cnt < cost){
	dis.clear();
	copy(P.begin(),P.end(),back_inserter(dis));
      }   
      cnt = cost;
    }
  }

}

int main(){
  int s1,s2,d;
 
  while(true){
    cin >> ns >> nl;
    if(ns+nl == 0)break;
    dis.clear();
    dis.push_back(9999999);
    for(int j=0;j<12;j++)for(int i=0;i<12;i++){
	vec[i][j]=INF;    
	used[j][i] = false;
      }
    cnt = 0;

    for(int i=0;i<nl;i++){
      cin >> s1 >> s2 >> d;
      vec[s1][s2] = vec[s2][s1] = d;
    }

    vector<int> pos;
    for(int i=1;i<=ns;i++){
      pos.push_back(i);
      
      permutation(i,0,pos);
      for(int k=0;k<12;k++)for(int j=0;j<12;j++)used[k][j] = false;
      pos.pop_back();
    }
    cout << cnt << endl;
    for(int i=0;i<dis.size();i++){
      cout << dis[i];
      if(i == dis.size()-1)cout<< endl;
      else cout << " ";
    }
  }
  return 0;
}

Measured memory_bytes: 1216
# DSL_3_C.py
def count_two_idx(A,q):
    ans = 0
    left = 0
    csum = 0
    for right in range(N):
        csum += A[right]
        while csum > q:
            csum -= A[left]
            left += 1
        ans += right - left + 1
    return ans


N, M = [int(x) for x in input().split()]
A = list(map(int, input().split()))
X = list(map(int, input().split()))

for q in X:
    print(count_two_idx(A,q))



Measured memory_bytes: 16612
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<ll, ll>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
const ll mod = 1000000007;
const double eps = 1E-18;

int main()
{
  string s;
  cin >> s;
  string ans = "Good";
  if (s[0]==s[1] || s[1]==s[2] || s[2]==s[3]) {
    ans = "Bad";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rgi register int
#define ll long long
class fastin{
	private: int _ch,_f;
	public: template<typename _Tp> inline fastin& operator>>(_Tp&_x){
		_x=0; while(!isdigit(_ch)) _f|=(_ch==45),_ch=getchar();
		while(isdigit(_ch)) _x=(_x<<1)+(_x<<3)+(_ch^48),_ch=getchar();
		_f&&(_x=-_x,_f=0); return *this;}
	fastin() {_ch=_f=0;}
}fin;
class fastout{
	private: int _num[32],_head;
	public: int SUF; template<typename _Tp> inline fastout& operator<<(_Tp _x){
		_Tp _k; if(_x==0) {putchar('0'),putchar(SUF);return *this;} if(_x<0) putchar('-'),_x=-_x;
		while(_x>0) _k=_x/10,++_head,_num[_head]=(_x-(_k<<1)-(_k<<3))^48,_x=_k;
		while(_head>0) putchar(_num[_head]),--_head; putchar(SUF); return *this;}
	fastout() {_head=0,SUF=' ';}
}fout;
// ----------------------------
// #define int ll
// using namespace std;
const int maxn=200004;
const int mod=998244353,inf=1000000007;

signed main()
{
	ll n,m;
	fin>>n>>m;
	fout<<((n*(n-1))/2+(m*(m-1))/2);
	return 0;
}
// ----------------------------
// by imzzy


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

using namespace std;

using ll = long long;
using ld = long double;

#define int long long
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

void accell() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}



signed main() {
    accell();
    int r;
    cin >> r;
    cout << r * r;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n,m=MI()
	x=LI()
	x.sort()
	A=[]
	for i,j in zip(x[1:],x[:-1]):
		A.append(i-j)
	#print(A)
	A.sort()
	print(sum(A[:max(m-n,0)]))


if __name__ == "__main__":
	main()


Measured memory_bytes: 91720
#include <bits/stdc++.h>
#define ll double
using namespace std;

int main(){
    ll sum=0;
    int n;
    cin>>n;
    ll p[n];
    ll dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=n;i++){
        dp[0][i]=(1-p[i])*dp[0][i-1];
        for(int j=1;j<=i;j++){
            dp[j][i]=(p[i]*dp[j-1][i-1])+(1-p[i])*dp[j][i-1];
        }
    }
    for(int i=n/2+1;i<=n;i++){
        sum+=dp[i][n];
    }
    cout<<setprecision(10)<<sum<<endl;

}




Measured memory_bytes: 70528
#include "bits/stdc++.h"

using namespace std;

void solve()
{
	int a, b;
	cin >> a >> b;
	cout << ((b%a) ? (b-a) : (a+b)) << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


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

#define int long long
#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
template <class T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> using v = vector<T>;
using P = pair<int, int>;

/*
 *  */

signed main() {
  string a, b, c;
  cin >> a >> b >> c;
  cout << a[0] << b[0] << c[0] << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
  
public class Main{
  public static void main(String[] args){
    Scanner stdIn=new Scanner(System.in);
    int i=0,count=0;
    int a=stdIn.nextInt();
    int b=stdIn.nextInt();
    System.out.printf("%d %d %.5f\n",a/b,a%b,(double)a/b);
  }
}



Measured memory_bytes: 26460
#include <stdio.h>
int main(void){
    int i,x[10];
    for(i = 1;i <= 5;i ++){
        scanf("%d", &x[i]);
    }
    for(i = 1;i <= 5;i ++){
        if(x[i] != i){
            printf("%d", i);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1680
/* ***********************************************
Author        :yang12138
Created Time  :2017年07月07日 星期五 18时09分44秒
File Name     :C.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

const int N=1e5+10;

struct Node{
	int pos,sub,id;
	Node(){}
	Node(int pos,int sub,int id){
		this->pos=pos;
		this->sub=sub;
		this->id=id;
	}
	bool operator < (const Node& tmp)const{
		if(pos==tmp.pos) return id<tmp.id;
		return pos<tmp.pos;
	}
}p[N<<3];

int a[N];
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",a+i);

	int cnt=0;
	ll ans=0;
	for(int i=1;i<n;i++){
		if(a[i]<a[i+1]){
			ans+=a[i+1]-a[i];
			if(a[i]+2<a[i+1]+1){
				p[cnt++]=Node(a[i]+2,0,2);
				p[cnt++]=Node(a[i+1]+1,-(a[i+1]-a[i]-1),1);
			}
		}
		else{
			ans+=a[i+1]-a[i]+m;
			if(a[i]+2<m+1){
				p[cnt++]=Node(a[i]+2,0,2);
				p[cnt++]=Node(m+1,-(m-a[i]-1),1);
			}
			p[cnt++]=Node(1,m+1-a[i]-2,2);
			p[cnt++]=Node(a[i+1]+1,-(a[i+1]-a[i]+m-1),1);
		}
	}

	sort(p,p+cnt);
	int tot=0,pre=1;
	ll tmp=ans;
	for(int i=0,j;i<cnt;i=j){

		j=i;
		while(j<cnt && p[j].pos==p[i].pos){
			if(p[j].id==1){
				tmp-=p[j].sub;
				tot--;
			}
			else{
				tmp-=p[j].sub;
				tot++;
			}
			j++;
		}
		if(j<cnt){
			int cur=p[j].pos;
			tmp-=(cur-pre)*tot;
			pre=cur;
		}

		ans=min(ans,tmp);
	}

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


Measured memory_bytes: 6400
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        k: usize,
        mut v: [i64; n]
    }
    v.sort();
    let mut l = -1000000000000000000;
    let mut r = 1000000000000000000;
    while l + 1 < r {
        let m = (l + r) / 2;
        let mut c = 0;
        for i in 0..n {
            if v[i] < 0 {
                let mut li = i;
                let mut ri = n;
                while li + 1 < ri {
                    let mi = (li + ri) / 2;
                    if v[mi] * v[i] >= m {
                        li = mi;
                    } else {
                        ri = mi;
                    }
                }
                c += n - ri;
            } else if v[i] == 0 {
                if m > 0 {
                    c += n - i - 1;
                }
            } else {
                let mut li = i;
                let mut ri = n;
                while li + 1 < ri {
                    let mi = (li + ri) / 2;
                    if v[mi] * v[i] >= m {
                        ri = mi;
                    } else {
                        li = mi;
                    }
                }
                c += li - i;
            }
        }
        if c < k {
            l = m;
        } else {
            r = m;
        }
    }
    println!("{}", l);
}


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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int n,m,ans;

main() {
    cin >> n >> m;
    if (n<m/2) ans+=n,m-=n*2,ans+=m/4;
    else ans=m/2;
    ct(ans)
}

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

using namespace std;

const int N = 1e5 + 5;

struct edge {
    int v;
    edge *next;
} pool[3 * N], *h[N];

int n, m, top = -1;
int size[N], ans;
int p[N], col[N], vis[N];
int circle = -1, S, T;
vector <int> V;

inline void addedge(int u, int v) {
    edge *tmp = &pool[++top];
    tmp -> v = v; tmp -> next = h[u]; h[u] = tmp;
}

void dfs_1(int u) {
    size[u] = col[u] = -col[p[u]];
    vis[u] = true;
    for(edge *tmp = h[u]; tmp; tmp = tmp -> next) {
        int v = tmp -> v;
        if(vis[v] && circle == -1 && v != p[u]) {
            S = u;
            T = v;
            circle = abs(col[u] + col[v]) / 2;
            continue;
        }
        if(vis[v]) continue;
        p[v] = u;
        dfs_1(v);
        size[u] += size[v];
    }
    ans += abs(size[u]);
}

void dfs_2(int u) {
    vis[u] = true;
    size[u] = col[u];
    for(edge *tmp = h[u]; tmp; tmp = tmp -> next) {
        int v = tmp -> v;
        if(vis[v]) continue;
        dfs_2(v);
        size[u] += size[v];
    }
    ans += abs(size[u]);
}

void init() {
    int x, y;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);       
    }
    col[0] = -1;
    dfs_1(1);

    if(m == n - 1) {
        if(size[1]) return (void) printf("-1\n");
    }
    else if(circle == 0) {
        if(size[1]) return (void) printf("-1\n");
        x = S;
        while(x != T) V.push_back(size[x]), ans -= abs(size[x]) , x = p[x];
        V.push_back(0);
        sort(V.begin(), V.end());
        y = V[V.size() / 2];
        for(auto x : V) ans += abs(x - y);
    }
    else {
        //for(int i = 1; i <= n; i++) printf("%d ", size[i]); printf("\n");
        if(abs(size[1]) & 1) return (void) printf("-1\n");
        col[S] -= size[1] / 2;
        col[T] -= size[1] / 2;
        ans = abs(size[1]) / 2;
        for(int i = 1; i <= n; i++) vis[i] = false;
        dfs_2(1);
    }
    printf("%d\n", ans);
}

int main() {
    cin >> n >> m;  
    init();
    return 0;
}

//tree?


Measured memory_bytes: 11644
#include<iostream>
#include<stdio.h>
#include<ext/rope>
using namespace std;
string a,b,c;
int main(){
    int i,n;
    cin>>n>>a>>b>>c;
    int ans=0;
    for(i=0;i<n;i++){
        if(a[i]==b[i]&&a[i]==c[i]&&b[i]==c[i]) continue;
        if(a[i]!=b[i]&&a[i]!=c[i]&&b[i]!=c[i]) ans+=2;
        else ans+=1;

    }
    cout<<ans<<endl;
    return 0;

}



Measured memory_bytes: 256
// Practice AtCoder
// author: Leonardone @ NEETSDKASU

fn main() {
    let mut stdin = String::new();
    std::io::Read::read_to_string(&mut std::io::stdin(), &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
        ($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let n = get!(usize);
    let mut edges = vec![vec![]; n + 1];
    for edge_id in 0..n - 1 {
        let vertex_a = get!(usize);
        let vertex_b = get!(usize);
        edges[vertex_a].push((vertex_b, edge_id));
        edges[vertex_b].push((vertex_a, edge_id));
    }
    let color_count = edges
        .iter()
        .map(Vec::len)
        .max()
        .unwrap();
     
     let mut edge_color = vec![0; n - 1];
     
     let mut dfs_stack = vec![1];
     
     while let Some(vertex) = dfs_stack.pop() {
         let mut used_color = vec![false; color_count + 1];
         for &(_, edge_id) in &edges[vertex] {
             used_color[edge_color[edge_id]] = true;
         }
         let mut color_id = 1;
         for &(end_vertex, edge_id) in &edges[vertex] {
             if edge_color[edge_id] == 0 {
                 dfs_stack.push(end_vertex);
                 while used_color[color_id] {
                     color_id += 1;
                 }
                 edge_color[edge_id] = color_id;
                 color_id += 1;
             }
         }
     }
     
     println!("{}", color_count);
     for color_id in edge_color {
         println!("{}", color_id);
     }
}

Measured memory_bytes: 16764
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int S,s1,s2,s3;
  cin >> S;
  s1=S / 100;
  s2=(S-s1*100) / 10;
  s3=S%10;
  cout << s1+s2+s3 << endl;
}

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<ll,ll> pll;
 
const int maxV = 90010;
const int maxN = 1e5+10;
const int MOD = 1e9+7;
const ll INF = 1000000000000000010LL;
const ll inf = 1e9+10;
 
 
ll a[maxN];

int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	priority_queue<int> Q;
	for(int i=1;i<=n;i++)
	{
		Q.push(a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int x = Q.top();
		Q.pop();
		x/=2;
		Q.push(x);
	}
	ll ans = 0;
	while(!Q.empty())
	{
		int x = Q.top();
		Q.pop();
		ans += x;
	}
	cout<<ans<<endl;
	return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second


int main(){
    ll n;
    cin >> n;
    ll cnt[9][9] = {}; //iから始まってjで終わる数の個数
    rep(i,1,n+1){
        ll temp = i;
        string t = "";
        while(temp){
            t += (temp % 10) + '0';
            temp /= 10;
        }
        if(t[0] == '0' || t[t.size()-1] == '0') continue;
        cnt[t[t.size()-1] - '1'][t[0] - '1']++;
    }

    ll ans = 0;
    rep(i,1,n+1){
        ll temp = i;
        string t = "";
        while(temp){
            t += (temp % 10) + '0';
            temp /= 10;
        }
        if(t[0] == '0' || t[t.size()-1] == '0') continue;
        ans += cnt[t[0] - '1'][t[t.size()-1] - '1'];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3584
//By Don4ick 
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qewr1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();		

	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	string s;
	cin >> s;
	int cnt = 0;
	ll ans = 0;
	for (int i = 0; i < (int)s.size(); i++)
	{
		if (s[i] == 'W')
			ans += cnt;
		else
			cnt++;
	}
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 720
#include <cstdio>

using namespace std;

int main()
{
	int a,b,c,n,total,kind;
	int rist[1000][3],ristsize;
	int isacheced[301];

	scanf("%d %d %d",&a,&b,&c);

	while(a != 0 && b != 0 && c != 0){
		scanf("%d",&n);

		total = a + b + c;
		ristsize = 0;
		for(int i = 0; i <= total; i++){
			isacheced[i] = 2;
		}
	
		for(int i = 0; i < n; i++){
			scanf("%d %d %d %d",&a,&b,&c,&kind);
			if(kind == 1){
				isacheced[a] = 1;
				isacheced[b] = 1;
				isacheced[c] = 1;
			}
			else{
				rist[ristsize][0] = a;
				rist[ristsize][1] = b;
				rist[ristsize][2] = c;
				ristsize++;
			}
		}
	
		for(int i = 0; i < ristsize; i++){
			if(isacheced[ rist[i][0] ] == 1 && isacheced[ rist[i][1] ] == 1){
				isacheced[ rist[i][2] ] = 0;
			}
			else if(isacheced[ rist[i][1] ] == 1 && isacheced[ rist[i][2] ] == 1){
				isacheced[ rist[i][0] ] = 0;
			}
			else if(isacheced[ rist[i][0] ] == 1 && isacheced[ rist[i][2] ] == 1){
				isacheced[ rist[i][1] ] = 0;
			}
		}
	
		for(int i = 1; i <= total; i++){
			printf("%d\n",isacheced[i]);
		}

		scanf("%d %d %d",&a,&b,&c);
	}

return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1, 0);
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        A[a]++;
    }
    sort(A.begin(), A.end());
    vector<int> sum(N+1);
    sum[1] = A[1];
    for (int i = 2; i <= N; i++) sum[i] = sum[i-1]+A[i];
    int cnt = 1;
    vector<int> ans(N+1, 0);
    for (int K = N; K >= 1; K--) {
        while(true){
            auto it = lower_bound(A.begin(), A.end(), cnt);
            int t = distance(it, A.end());
            if (t*cnt+sum[N-t] < K*cnt) break;
            else cnt++;
        }
        ans[K] = cnt-1;
    }
    for (int i = 1; i <= N; i++) cout << ans[i] << endl;
    return 0;
}


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

int main(){
    int x,y;
    while (true){
        cin >> x >> y;
        if (x == 0 && y == 0){
            break;
        }
        cout << min(x,y) << " " << max(x,y) << endl;
    }
    return 0;
}


Measured memory_bytes: 3088
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

H,W = II()
S = [str(input()) for _ in range(H)]

d = [(0,1),(0,-1),(1,0),(-1,0)]
visited = [[False]*W for _ in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        else:
            whites = 0
            blacks = 0
            p = [(i,j)]
            while p:
                now = p.pop()
                if S[now[0]][now[1]]=='#':
                    blacks += 1
                else:
                    whites += 1
                visited[now[0]][now[1]] = True
                for d0 in d:
                    new = (now[0]+d0[0],now[1]+d0[1])
                    if 0<=new[0]<=H-1 and 0<=new[1]<=W-1:
                        if S[now[0]][now[1]]!=S[new[0]][new[1]] and (not visited[new[0]][new[1]]):
                            p.append(new)
                            visited[new[0]][new[1]] = True
            ans += whites*blacks
print(ans)

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

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

    long long a, b, k;
    cin >> a >> b >> k;

    if(a <= k){
        k -= a;
        a = 0;
    }else{
        a -= k;
        k = 0;
    }

    if(b <= k){
        k -= b;
        b = 0;
    }else{
        b -= k;
        k = 0;
    }

    cout << a << ' ' << b << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#include <fstream>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define LL long long
#define LI long int
#define LLI long long int
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int n;
VE g[51];
bool connect(int s,int t);

int main(){
    int m; cin>>n>>m;
    int a[2500],b[2500];
    FOR(i,0,m){
        int s,t;
        cin>>s>>t;
        a[i]=s; b[i]=t;
        g[s].PB(t);
        g[t].PB(s);
    }
    int ans=0;
    FOR(i,0,m){
        //cout<<connect(a[i],b[i])<<endl;
        if(!connect(a[i],b[i])) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

bool connect(int s,int t){
    stack<int> st;
    int color[51]={0};
    color[s]=1;
    st.push(s);
    while(!st.empty()){
        int u=st.top();
        st.pop();
        FOR(i,0,g[u].size()){
            int v=g[u][i];
            if(color[v]==0&& !(u==s&&v==t)){
                color[v]=1;
                st.push(v);
            }
        }
    }
    return color[s]==color[t];
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  ll a,v,b,w,t; cin >> a >> v >> b >> w >> t;
  if(a == b){
    cout << "YES" << endl;
  } else if(v <= w){
    cout << "NO" << endl;
  } else if((v-w)*t >= abs(a-b)){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define endl "\n"
#define loop(i,s,e) for(int i=s;i<e;i++)
// #define int long long
#define mp make_pair
#define pii pair<int,int>
#define mset(a,f)  memset(a , f , sizeof(a))
#define pb push_back
const int N = 3e5 + 6;
const int M = 1e9 + 7;
// const int inf = 1e17;


// bool J27 = 1;
#define bug(...)                                  __f (#__VA_ARGS__, __VA_ARGS__)
#define rtn                                       if(0)return;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { rtn cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{     rtn 
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
 

int A[N];
int n,a,b;
int dp[2][N];


void solve()
{

	cin >> n >> a;

	loop(i,1,n+1)cin >> A[i];

	mset(dp,0);

	dp[0][0] = 1;

	loop(i,1,n+1)
	{
		loop(j,0,a+1)
		{
			int ans = 0;
			ans = dp[(i-1)%2][j];
			if(j-1 >= 0)ans += dp[i%2][j-1],ans%M;
			if(j-1 >= A[i])ans -= dp[(i-1)%2][j-1-A[i]];
			if(ans < 0)ans += M;
			dp[i%2][j] = ans%M;
		}
	}

	cout << dp[n%2][a];

	// cout << alpha(n,a);
}
 
int32_t main()
{
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

 	
 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int p = s.nextInt();
		int m = s.nextInt();
		int c = s.nextInt();
		
		System.out.println(p+m+c);
		
		
	}
}

Measured memory_bytes: 26240
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
#include <unordered_map>
  
using namespace std;
 
template <typename T>
class UF{
public:
    T par[5000],rank[5000];
  
    inline UF(T n){
        for(T i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }
  
    inline T find(T x){
        if(par[x]==x)
            return x;
        else
            return par[x]=find(par[x]);
    }
  
    inline void unite(T x, T y){
        x=find(x);
        y=find(y);
        if(x==y) return;
  
        if(rank[x]<rank[y])
            par[x]=y;
        else{
            par[y]=x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
  
    inline bool same(T x, T y){
        return find(x)==find(y);
    }
  
};

int main(){
	int n;
	cin>>n;
	UF<int> uf(n);	
	unordered_map<string,int> id;
	
	string s,s2;
	int x,cost[5000];
	for(int i=0;i<n;i++){
		cin>>s>>x;
		cost[id[s]=i]=x;
	}
	
	int q;
	cin>>q;
	while(q--){
		cin>>s>>s2;
		uf.unite(id[s],id[s2]);
	}
	
	for(int i=0;i<n;i++){
		x=uf.find(i);
		cost[x]=min(cost[x],cost[i]);
	}

	int ans=0;
	for(int i=0;i<n;i++){
		ans+=cost[uf.find(i)];
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3756
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

n=int(input().rstrip())
a=sorted([int(i) for i in input().split()],reverse=1)
nokori=n-2
i=1
ans=a[0]
while nokori>1:
    ans+=a[i]*2
    nokori-=2
    i+=1
if n%2:ans+=a[i]
print(ans)

Measured memory_bytes: 31456
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>

int main()
{
    char c[105];
    scanf("%s",c);
    int ans=0;
    int l=strlen(c);
    for (int i=0;i<l;i++)
        if (c[i]=='+') ans++; else ans--;
    printf("%d\n",ans);
     return 0;
}


Measured memory_bytes: 256
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    h, w, k = LI()
    cake = []
    for _ in range(h):
        row = S()
        row = row.replace(".", "0").replace("#", "1")
        row = list(map(int, row))
        cake.append(row)

    s = [0]
    g = []
    rsum = [sum(cake[i]) for i in range(h)]
    for i in range(h):
        if rsum[i] != 0:
            rsum[i] = 0
            break
    for i in range(h):
        if rsum[i] != 0:
            s.append(i)
            g.append(i)
    g.append(h)

    cnt = 0
    ans = []

    for i in range(len(s)):
        row_t = list(zip(*cake[s[i]:g[i]]))
        tsum = [sum(row_t[j]) for j in range(len(row_t))]
        for j in range(len(row_t)):
            if tsum[j] != 0:
                tsum[j] = 0
                break
        cnt += 1
        for j in range(len(row_t)):
            if tsum[j] == 1:
                cnt += 1
            row_t[j] = [cnt for _ in range(len(row_t[j]))]
        row = list(zip(*row_t))
        ans += row

    for row in ans:
        print(*row)


main()





Measured memory_bytes: 74708
object Main {
  def main(args: Array[String]) {
    val input = io.Source.stdin.getLines().mkString("\n")
    println(kagamiMochi(input).trim())
  }

  def kagamiMochi(input: String) :String = {
    //先頭の要素を除外する
    //新しいコレクションを作る

    //要素にある数字が何個あるかカウントする
    //同じ数字が2つ以上ある時、その数字のみ残す
    //同じ数字が4つ以上ある時、
    //その組が2つ以上なければ0を出力する
    //2つずつ以上ある数字を掛け算する
    //最大値を出力する

    val map = input.split("\n")(1).split(" ").map(_.toLong).groupBy(identity).mapValues(_.size).filter(n => (n._2 >= 2))
    if(map.isEmpty) return "0"

    //4以上の値が無いときが考慮されていない
    val square = map.filter(n => n._2 >=4)
    val squareMax = if(!square.isEmpty) Some(square.map(n => (n._1 * n._1)).max) else Some(0L)

    //mapのkey値を任意の2つ抜き出して掛け算する
    val aaaa = map.keys.toSeq.sorted.takeRight(2).product
    if(aaaa > squareMax.getOrElse(0L)) return aaaa.toString else squareMax.get.toString
  }


}

Measured memory_bytes: 110192
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000000000000007;
const int MOD=1000000007;
signed main(){
  int n,m,R;cin>>n>>m>>R;
  vector<int> r(R);
  rep(i,R){
    cin>>r[i];
  }
  vector<vector<int>> dp(n+1,vector<int>(n+1,inf));
  rep(i,m){
    int a,b,c;cin>>a>>b>>c;
    dp[a][b]=c;
    dp[b][a]=c;
  }
  rep1(k,n){
    rep1(i,n){
      rep1(j,n){
        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
      }
    }
  }
  int res=inf;
  sort(r.begin(),r.end());
  do{
    int buf=0;
    rep1(i,R-1){
      buf+=dp[r[i-1]][r[i]];
    }
    res=min(res,buf);
  }while(next_permutation(ALL(r)));
  cout<<res<<"\n";
  return 0;
}


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

int main()
{
	int c1, c2, c3, cnt;
	while (cin>>c1>>c2>>c3)
	{
		int card[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		card[c1] = -1;
		card[c2] = -1;
		card[c3] = -1;
		cnt = 0;
		for (int i = 1; i < 11; i++)
		{
			if (card[i] != -1)
			{
				if (c1 + c2 + i <= 20)
				{
					cnt++;
				}
			}
		}
		if (cnt>=4)		// (残りカード7枚) * 0.5
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}

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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  int n;
  ll c;
  cin >> n >> c;

  vector<pair<ll, ll>> v_xv(n);
  vector<ll> f1(n + 1, 0), f2(n + 1, 0);
  ll v_sum = 0;
  for (int i = 0; i < n; i++) {
    auto &p = v_xv[i];
    cin >> p.first >> p.second;
    v_sum += p.second;
    f1[i + 1] = max(f1[i], v_sum - p.first);
    f2[i + 1] = max(f2[i], v_sum - p.first * 2);
  }

  // 左に一回も歩かない場合
  ll ans = f1.back();

  v_sum = 0;
  for (int i = 0; i < n; ++i) {
    auto &p = *(v_xv.rbegin() + i);
    v_sum += p.second;
    ll l_dist = c - p.first;

    ll l_max = v_sum - l_dist;
    ll l_ans = l_max;
    if (i != n - 1) {
      ll r_max1 = *(f1.rbegin() + i + 1), r_max2 = *(f2.rbegin() + i + 1);
      l_ans = max(l_max + r_max1 - l_dist, l_max + r_max2);
    }

    ans = max(ans, l_ans);
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 3328
n, m = map(int, input().split())
x = [0] * (n+2)
for i in range(m):
    l, r = map(int, input().split())
    x[l] += 1
    x[r+1] -= 1

ans = 0
for i in range(1, n+1):
    x[i] += x[i-1]
    if x[i] == m:
        ans += 1
print(ans)


Measured memory_bytes: 12664
#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll>
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>x;i--)
typedef long long ll;
using namespace std;

int main(){
    ll N;
    cin >> N;
    vector<ll> P(N);
    REP(i,0,N){
        cin>>P.at(i);
    }
    ll ans=0;
    ll ma=0;
    REP(i,0,N){
        ans+=P.at(i);
        ma = max(P.at(i),ma);
    }
    cout<<ans-ma/2<<endl;
}



Measured memory_bytes: 256
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const int N=250010;

pii b[N],d[N];
int c[N],s[N],ans[N];

int main()
{
	int n;scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&b[i].x);b[i].y=i;
		c[b[i].x]=i;
	}
	sort(b+1,b+n+1);
	int k=1;for (int i=1;i<=n;i++) s[i]=0;
	int m=0,q=1;
	for (int i=1;i<=n*n;i++)
		if (c[i])
		{
			s[c[i]]++;
			if (s[c[i]]<c[i]) {puts("No");return 0;}
			ans[i]=c[i];d[++m].x=c[i];d[m].y=n-c[i];
		}
		else
		{
			while (k<=n&&s[b[k].y]>=b[k].y-1) k++;
			if (k<=n)
			{
				s[b[k].y]++;ans[i]=b[k].y;
			}
			else
			{
				while (q<=m&&!d[q].y) q++;
				if (q>m) {puts("No");return 0;}
				ans[i]=d[q].x;d[q].y--;
			}
		}
	puts("Yes");
	for (int i=1;i<n*n;i++) printf("%d ",ans[i]);
	printf("%d\n",ans[n*n]);
	return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

int parent(int i){
    return i/2;
}
 
int left(int i){
    return 2*i;
}
 
int right(int i){
    return 2*i +1;
}
 
int maxheapify(vector <int> &X, int i){
    int l, r;
    l = left(i);
    r = right(i);
 
    if (r <=X[0] && X[l] < X[r] && X[r] > X[i]){
        swap(X[r], X[i]);
        maxheapify(X, r);
    }
    else if (l <= X[0] && X[l] > X[i]){
        swap(X[l], X[i]);
        maxheapify(X, l);
    }
    return 0;
}
 
int buildmaxheap(vector <int> &X){
    int hsize = X[0];
    for (int i= hsize/2; i>0; i--){
        maxheapify(X, i);
    }
    return 0;
}
 
int maxheapinsert(vector <int> &X, int key){
    if (X[0]<X.size()-1){
        X[0]++;
        X[X[0]] = key;
    }
    else{
        X[0]++;
        X.push_back(key);
    }
    int i = X[0];
    while (i > 1 && X[parent(i)] < X[i]){
        swap(X[i], X[parent(i)]);
        i = parent(i);
    }
    return 0;
}
 
int heapincreasekey(vector <int> &X, int i, int key){
    if (i > X[0] || key < X[i]) return NULL;
    X[i] = key;
    while (i > 1 && X[parent(i)] < X[i]){
        swap(X[i], X[parent(i)]);
        i = parent(i);
    }
    return 0;
}
 
int heapextractmax(vector <int> &X){
    if (X[0] < 1) return NULL;
 
    int maxheap = X[1];
    X[1] = X[X[0]--];
    maxheapify(X, 1);
    return maxheap;
}
 
int main(void){
 
    vector <int> X(1);
    X[0] = 0;
    string text;
	int n;

	while (true){
        cin>>text;
        if (text[2] == 'd'){
            break;
        }
        else if (text[0] == 'i'){
			cin>>n;
            maxheapinsert(X, n);
        }
        else if (text[0] == 'e'){
            cout<<heapextractmax(X)<<endl;
        }
    }
    return 0;
} 

Measured memory_bytes: 7280
#coding:UTF-8
class Node:
    def __init__(self,point):
        self.n=point
        self.left=None
        self.right=None
        
def insert(t,z):
    y=None
    x=t
    while x!=None:
        y=x
        if z.n<x.n:
            x=x.left
        else:
            x=x.right
    if y==None:
        return z
    else:
        if z.n<y.n:
            y.left=z
        else:
            y.right=z
        return t

def Find(t,p):
    if t.n == p:
        return True
    elif t.left!=None and t.n>p:
        a=Find(t.left,p)
    elif t.right!=None and t.n<p:
        a=Find(t.right,p)
    else:
        return False
    return a

def Pre(t,l):
    l.append(str(t.n))
    if t.left!=None:
        Pre(t.left,l)
    if t.right!=None:
        Pre(t.right,l)

def In(t,l):
    if t.left!=None:
        In(t.left,l)
    l.append(str(t.n))
    if t.right!=None:
        In(t.right,l)

def BST2(A,n):
    tree=None
    for i in range(n):
        if A[i]=="print":
            PreAns=[]
            InAns=[]
            Pre(tree,PreAns)
            In(tree,InAns)
            print(" "+" ".join(InAns))
            print(" "+" ".join(PreAns))
        else:
            if A[i].split(" ")[0]=="find":
                c="no"
                point=int(A[i].split(" ")[1])
                if Find(tree,point)==True:
                    print("yes")
                else:
                    print("no")
                
            else:    
                z=Node(int(A[i].split(" ")[1]))
                tree=insert(tree,z)
            
if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(input())
    BST2(A,n)

Measured memory_bytes: 186332
N, X = gets.split.map{|i|i.to_i}
a = gets.split.map{|i|i.to_i}
count = 0
N.times{|i|
    sum = a[i]
    if i > 0
        sum += a[i - 1]
    end
    if sum > X
        a[i] -= sum - X
        count += sum - X
    end
}
puts count


Measured memory_bytes: 8580