akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

const int MOD =  1e9 + 7;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

bool gap;
int dp[3001][3001];

int solve(vector<int>&v,int l,int r)
{
    if(l > r) return 0;

    if(dp[l][r] != -1) return dp[l][r];

    if(((r-l)&1) != gap)
    {
        return dp[l][r] = max(v[l] + solve(v,l+1,r),v[r] + solve(v,l,r-1));
    }

    // cout<<l<<" "<<r<<endl;
    
    return dp[l][r] = min(-v[l] + solve(v,l+1,r),-v[r] + solve(v,l,r-1));
}

int32_t main()
{
	FASTIO;

	int n;
    cin>>n;

    memset(dp,-1,sizeof dp);

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

    if(n&1) gap = true;
    else gap = false;

    cout<<solve(v,0,n-1);


}

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

#define ll long long
using namespace std;

const int N = 2e5 + 5;
int n, h[N];
ll a[N], tree[4 * N], lazy[4 * N];

void prop(int i, int l, int r) {
    tree[i] = max(tree[i], lazy[i]);
    if(l < r) {
        lazy[2 * i + 1] = max(lazy[2 * i + 1], lazy[i]);
        lazy[2 * i + 2] = max(lazy[2 * i + 2], lazy[i]);
    }
    lazy[i] = 0;
}
ll query(int i, int l, int r, int L, int R) {
    if(r < L || R < l) return 0;
    prop(i, l, r);
    if(L <= l && r <= R) return tree[i];
    int m = (l + r) / 2;
    return max(query(2 * i + 1, l, m, L, R), query(2 * i + 2, m + 1, r, L, R));
}
void upd(int i, int l, int r, int L, int R, ll x) {
    prop(i, l, r);
    if(r < L || R < l) return;
    if(L <= l && r <= R) {
        lazy[i] = max(lazy[i], x);
        prop(i, l, r);
        return;
    }
    int m = (l + r) / 2;
    upd(2 * i + 1, l, m, L, R, x);
    upd(2 * i + 2, m + 1, r, L, R, x);
    tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        upd(0, 1, n, h[i], n, a[i] + query(0, 1, n, h[i], h[i]));
    }
    cout << query(0, 1, n, n, n) << endl;
}

Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 


int main() {
	string s;
	cin>>s;
	for(int i=1;i<s.size();i++){
		if(s[i-1]==s[i]){
			cout << i << " "<< i+1;
			return 0;
		}
	}
	if(s.size()==2){
		cout << "-1 -1";
		return 0;
	}
	for(int i=2;i<s.size();i++){
		if(s[i-2]==s[i]){
			cout << i-1 <<" "<< i+1;
			return 0;
		}
	}
	cout << "-1 -1";
}

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

int sumOfDigit(int n){
    int ans = 0;
    while(n>0){
        ans += n%10;
        n /= 10; 
    }
    return ans;
}

int main() {
    int ans = 0;
    int n,a,b;
    cin >> n >> a >> b;

    for(int i=0;i<n+1;i++){
        int sum = sumOfDigit(i);
        //cout << i << endl;
        if(a<=sum&&sum<=b)ans+=i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())

ans = 0
for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            if X == 500 * a + 100 * b + 50 * c:
                ans += 1
print(ans)


Measured memory_bytes: 9120
from collections import deque

N, M = map(int, input().split())
graph = [set() for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

def bfs(graph):
    visited = set()
    queue = deque()
    queue.append(1)
    ans = [0] * (N+1)
    while queue:
        cur = queue.popleft()
        visited.add(cur)
        for n in graph[cur]:
            if ans[n] == 0:
                ans[n] = cur
                queue.append(n)
    return ans

ans = bfs(graph)
print("Yes")
for i in range(2, len(ans)):
    print(ans[i])

Measured memory_bytes: 125436
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;++i)
#define mod 1000000007



int main(){
  float t,x;
  cin >> t >>x;

  float ans=0,res=0;
  ans=t/x;

  cout << ans << endl;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
ans=[]
for i in range(h):
  for j in range(w-1):
    if a[i][j]%2:
      a[i][j+1]+=1
      ans.append([i+1,j+1,i+1,j+2])
  if i<h-1 and a[i][w-1]%2:
    a[i+1][w-1]+=1
    ans.append([i+1,w,i+2,w])
print(len(ans))
for t in ans:
  print(*t)

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

int main() {
	ll n;
	cin >> n;
	--n;
	ll ans;
	if(n%2 == 0) {
		ans = (n/2) * (n+1);
	}
	else {
		ans = (n) * ((n+1)/2);	
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <numeric>
using namespace std;

const double PI=acos(-1);

int main(){
    string s;
    cin >> s;
    bool a[26] = {false}, z = true;
    for(int i = 0; i < s.length(); i++){
        a[s[i]-'a'] = true;
    }
    for(int i = 0; i < 26; i++){
        if(!a[i]){
            z = false;
            printf("%c\n", 'a'+i);
            break;
        }
    }
    if(z) cout << "None" << endl;
    return 0;
}

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

int main() {
    string s, t;
    cin >> s >> t;
    int ans = 10000;
    for(int i = 0; i <= s.size() - t.size(); i++) {
        int c = 0;
        for(int j = i, k = 0; j < i + t.size(); j++, k++) {
            if(s[j] != t[k]) {
                c++;
            }
        }
        ans = min(ans, c);
    }

    cout << ans;
}

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



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

    ll fib[N+1];
    fib[0] = 1;
    fib[1] = 1;

    for (int i=2; i<=N; i++) fib[i] = fib[i-1] + fib[i-2];

    cout << fib[N] << endl;

    return 0;
}




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





int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  ll N, M;
  cin >> N >> M;
  vector<ll> A(N);
  for (ll i=0; i<N; i++){
    cin >> A[i];
  }
  ll temp=0;

  map<ll,ll> count;
  vector<ll> elem;

  count[0]=1;
  elem.push_back(0);
  for (ll i: A){
    temp=(temp+i)%M;
    //cout<<temp<<endl;
    if (count.find(temp)!=count.end()){
      count[temp]++;
    } else{
      count[temp]=1;
      elem.push_back(temp);
    }
  }
  ll ans=0;
  for (ll i=0; i<elem.size(); i++){
    ll curr=count[elem[i]];
    ans+=(long long) curr*(curr-1)/2;
  }
  cout<<ans<<endl;
  
  //for (ll i:elem) {cout<<i<<" "<<count[i]<<endl;}
  

  
} 

Measured memory_bytes: 5496
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
	string s;
	long long dp[20]={0},sum = 0, res = 0,x = 0;
	cin >> s;
	dp[0] = 0;
	for(int i=1;i<=s.size();i++){
		res *= 10;
		res += (s[i-1]-'0')*pow(2,i-1);
		dp[i] += x + res;
		x += dp[i];
	}
	cout << dp[s.size()] << endl;
}

Measured memory_bytes: 512
//Author : Sukarna Paul

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/detail/standard_policies.hpp>
#define pi acos(-1)
#define pb push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}

using namespace std;
using namespace __gnu_pbds;

typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>pref_trie;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;




int main(){
    IOS
    //freopen("output.txt","w",stdout);
    string s,t;
    cin>>s>>t;

    string str(t.begin(),t.begin()+s.length());
    if(str==s){
        cout<<"Yes\n";
    }
    else{
        cout<<"No\n";
    }
}


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

char incrementChar(char x){
    return static_cast<char>(x + 1);
}

int main(){
    int K, X;
    cin >> K >> X;

    if(K * 500 >= X){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int G[103][103];
int more[103];
const int INF=-9;
bool know(int a,int b){//aがbを知っていたらtrue
	if(G[a][b]==1)return true;
	return false;
}
int main(){
	int n,m,p,ans=-1;
	while(true){
	cin>>n;
	if(n==0)break;
	ans=-1;
	for(int i=0;i<102;i++)for(int j=0;j<102;j++)G[i][j]=-2;
	for(int i=1;i<=n;i++){
		int tmp;
		cin>>tmp;
		for(int j=0;j<tmp;j++){
			cin>>p;
			G[i][p]=1;
		}
	}
	cin>>m;
	for(int i=0;i<m;i++)cin>>more[i];
	bool f=0;

	for(int i=1;i<=n;i++){
		f=1;
		for(int j=0;j<m;j++){
		if(know(i,more[j])==0)f=0;//知らなければ容疑者から除外
		//cout<<i<<" "<<more[j]<<" "<<know(i,more[j])<<endl;
		}
		if(f&&ans==-1)ans=i;
		else if(f&&ans!=-1){ans=-1;break;}
	}
	cout<<ans<<endl;
	}
	return 0;
}

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

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

    int len = s.length();
    char a;
    int ans = 0;
    int cou = 0;
    vector<int> q;
    int frag = 0;

    while(1){

        if(len == 0){
            break;
        }
        a = s[0];
        q.erase(q.begin(), q.end());
        q.push_back(0);
        cou = 1;
        for(int j = 1; j < len; j++){
            if(s[j] == a){
                cou++;
                q.push_back(j);
            }
        }

        if(cou % 2 != 0){
            frag = 1;
            break;
        }else{
            for(int j = cou - 1; j >= 0; j--){
                s.erase(q[j], 1);
            }
            len -= cou;
        }
    }

    if(frag == 1){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(1, N):
        X, Y = S[:i], S[i:]
        cnt = 0
        memo = []
        for letter in X:
            if letter not in memo:
                memo.append(letter)
                if letter in Y:
                    cnt += 1
        if cnt > ans:
            ans = cnt
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll n,q,sum=0;
  cin>>n;
  vector<ll> a(n),s(100001,0);
  for(ll i=0;i<n;i++){
    scanf("%lld",&a[i]);
    s[a[i]]++;
    sum+=a[i];
  }
  cin>>q;
  vector<ll> b(q),c(q);
  for(ll i=0;i<q;i++){
    scanf("%lld%lld",&b[i],&c[i]);
    sum+=(c[i]-b[i])*s[b[i]];
    s[c[i]]+=s[b[i]];
    s[b[i]]=0;
    cout<<sum<<endl;
  }
}

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

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

const int INF=1e9;
const int MOD=1e9+7;

int main(){
    string s; cin >> s;
    if(s.back()=='s'){
        cout << s << "es" << endl;
    }else{
        cout << s << 's' << endl;
    }
}

Measured memory_bytes: 3568
#include <iostream>

using namespace std;

int main() {
  int N;
  cin >> N;
  const char* result = "No";
  for (int i = 1; i <= 9; ++i) {
    for (int j = 1; j <= 9; ++j) {
      if (i * j == N) {
        result = "Yes";
        break;
      }
    }
  }
  cout << result << endl;
  return 0;
}


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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPr(i, n) for(int i = (n)-1; i >= 0; --i)
#define FORq(i, m, n) for(int i = (m); i <= (n); ++i)
#define FORqr(i, m, n) for(int i = (n); i >= (m); --i)
#define MP make_pair
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x, 0, sizeof(x))
#define FILL(x, y) memset(x, y, sizeof(x))
#define MM(x) memset(x, -1, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define DB(x) cerr << #x << " = " << x << endl
#define DB2(x, y)                                                              \
    cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define DEBUG                                                                  \
    int x12345;                                                                \
    cin >> x12345;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
const long long MOD = 1e9 + 7;
///////////////////////////////////////////////
// for template
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////
/// 🍈( '-' 🍈 |AC|
int main() {
    vector<int> ans(10002);
    int N; cin >> N;
    FORq(x,1,101){
        FORq(y,1,101){
            FORq(z,1,101){
                int K = x * x + y * y + z * z + x*y + y*z + z*x;
                if (K > N) continue;
                ans[K]++;
            }
        }
    }
    
    FORq(i,1,N){
        cout << ans[i] << "\n";
    }
}

Measured memory_bytes: 3592
N     = int(input())
lst_S = [input() for i in range(N)]

def main(lst_S):
    
    lst_S = sorted(lst_S)

    prev_S = lst_S[0]
    count  = 1
    S_with_count = {}
    for S in lst_S[1:]:

        if S == prev_S:
            count += 1
        else:
            S_with_count[prev_S] = count
            count = 1

        prev_S = S

    else:
        S_with_count[S] = count
    
    max_count = max(list(S_with_count.values()))
    answer_S  = []
    for key, value in sorted(
        S_with_count.items(), key=lambda x: x[1], reverse=True
        ):
        if value == max_count:
            answer_S.append(key)
        
    return sorted(answer_S)
        
if __name__ == "__main__":

    lst_answer = main(lst_S)
    for answer in lst_answer:
        print(answer)


Measured memory_bytes: 46372
#include<iostream>
#include<vector>
#include<cmath>
#define f(x,y) fabs((double)x/2-y)
using namespace std;
int main() {
	int w, h, x, y;
	bool yj=false;
	cin >> w >> h >> x >> y;
	cout << (double)w * h / 2<<" ";
	if (2*x==w&&2*y==h)cout << 1 << endl;
	else cout << 0 << endl;
	return 0;
	
	
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll H,W,N;
ll sh,sw;
string S,T;
int main(){
    cin>>H>>W>>N;
    cin>>sh>>sw;
    cin>>S>>T;

    ll narrowed[4]={};
    string plusC= "LRUD";
    string minusC="RLDU";
    ll limit[4]={W,W,H,H};
    ll start[4]={sw,sw,sh,sh};

    for(ll i=0;i<4;i++){
        for(ll j=N-1;j>=0;j--){
            if( T[j]==minusC[i] && narrowed[i]>0 ) narrowed[i]--;
            if( S[j]==plusC[i] ) narrowed[i]++;
            if( narrowed[i]>=limit[i] ){
                cout<<"NO";
                return 0;
            }
        }
    }
    if(sw<narrowed[0]+1 || W-narrowed[1]<sw || sh<narrowed[2]+1 || H-narrowed[3]<sh){
        cout<<"NO";
        return 0;
    }
    cout<<"YES";
    return 0;
}

Measured memory_bytes: 776
#include<algorithm>
#include<cstdio>
#include<cstring>
  
const int Maxv = 100010; 
int l[Maxv << 1], r[Maxv << 1], n; 
long long ans; 
  
inline int read(){
    int x = 0, f = 1; 
    char ch = getchar(); 
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1; 
        }
        ch = getchar(); 
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0'; 
        ch = getchar(); 
    }
    return x * f; 
}
  
int main(){
    n = read(); 
    for (int i = 1; i <= n; i++) {
        int L = read(); 
        int R = read(); 
        l[Maxv + R]++; 
        r[Maxv + L]++; 
    }
    l[Maxv]++; 
    r[Maxv]++; 
    for (int i = 1; i < 2 * Maxv; i++) {
        l[i] += l[i - 1]; 
    }
    for (int i = 2 * Maxv - 2; i >= 0; i--) {
        r[i] += r[i + 1]; 
    }
    for (int i = 0; i < 2 * Maxv - 1; i++) {
        ans += std::min(l[i], r[i + 1]) * 2; 
    }
    printf("%lld\n", ans); 
    return 0; 
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define db(x) cout<<#x<<"="<<x<<endl
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define y1 y1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
#define EPS 1e(-9);
using namespace std;
typedef long long ll;

void Main(){

  string S,T; cin>>S>>T;
  int ct=0;
  rep(i,3){
    ct+= S[i]==T[i];
  }
  cout<< ct<<"\n";
}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


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

int main()
{
	while (true)
	{
		int m, f, r;
		cin >> m >> f >> r;
		if (m == -1 && f == -1 && r == -1) break;
		if (m == -1 || f == -1)
		{
			cout << 'F' << endl;
			continue;
		}
		if (m + f >= 80)
		{
			cout << 'A' << endl;
			continue;
		}
		if (m + f >= 65)
		{
			cout << 'B' << endl;
			continue;
		}
		if (m + f >= 50)
		{
			cout << 'C' << endl;
			continue;
		}
		if (m + f < 30)
		{
			cout << 'F' << endl;
			continue;
		}
		if (r >= 50)
		{
			cout << 'C' << endl;
			continue;
		}
		cout << 'D' << endl;
	}
}


Measured memory_bytes: 3072
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
int n, k, cnt[N];
long long ans;
int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++) cnt[i % k] ++;
	for(int i = k; i <= 2 * n; i += k) if(!(i & 1)) {
		int a = ((k - (i >> 1)) % k + k) % k;
		ans += 1ll * cnt[a] * cnt[a];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    bool is_first_player_winning = false;
    rep (i, n) {
        cin >>a[i];
        if (a[i] % 2 == 1) {
            is_first_player_winning = true;
        }
    }
    cout << (is_first_player_winning ? "first" : "second") << endl;

}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}


int main(void) {
	int64 A[3];
	REP(i, 3) cin >> A[i];
	if (A[0] + A[1] + A[2] >= 22) {
		cout << "bust" << endl;
	} else {
		cout << "win" << endl;
	}
}


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

int main(){
  int N;
  string S;
  cin >> N >> S;
  int ans=0;
  for(int i=1;i<N;i++){
    string T=S.substr(0,i);
    string U=S.substr(i,N-i);
    set<int> st,sand;
    for(int j=0;j<T.size();j++){
      st.insert(T.at(j));
    }
    for(int j=0;j<U.size();j++){
      if(st.count(U.at(j))){
        sand.insert(U.at(j));
      }
    }
    if(ans<sand.size()){
      ans=sand.size();
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

struct Node_struct{
    int id, par, dep, left, right, sib, height;
};
typedef struct Node_struct Node;
Node node[200000];

int abc(int, int);

int main(){
    int i,j,k,n,id,left,right,deg,root;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        node[i].par = node[i].left = node[i].right = node[i].sib = -1;
    }
    for(i=0; i<n; i++){
        scanf("%d%d%d",&id, &left, &right);
        node[id].id = id;
        node[id].left = left;
        node[id].right = right;
        if(left != -1){
            node[left].par = id;
            node[left].sib = right;
        }   
        if(right != -1){
            node[right].par = id;
            node[right].sib = left;
        }
    }
    for(i=0; i<n; i++) if(node[i].par == -1) root = i;
    abc(root, 0);
    for(i=0; i<n; i++){
        deg = (node[i].left != -1) + (node[i].right != -1);
        printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",node[i].id, node[i].par, node[i].sib, deg, node[i].dep, node[i].height);
        if(node[i].par == -1)printf("root\n");
        else if(node[i].left == -1 && node[i].right == -1)printf("leaf\n");
        else printf("internal node\n");
    }
    return 0;
}

int abc(int pos, int dep){
    node[pos].dep = dep;
    int a=0,b=0;
    if(node[pos].left != -1) a=abc(node[pos].left, dep+1);
    if(node[pos].right != -1) b=abc(node[pos].right, dep+1);
    node[pos].height = a<b? b:a;
    return node[pos].height+1;
}


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

int main() {
 int n; cin >> n;
 vector<int> L(n);
 for(int i=0;i<n;i++){
   cin >> L[i];
 }
 int ans=0;
 sort(L.begin(),L.end());

 for(int i=0;i<n;i++){
   for(int j=0;j<i;j++){
     int ab=L[i]+L[j];
     int left=i+1;
     int right=lower_bound(L.begin(),L.end(),ab)-L.begin();
     ans+=right-left;
   }
 }
 cout << ans << endl;
}


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

int main(void) {
  string S, T, U;
  int A, B;
  cin >> S >> T >> A >> B >> U;
  if (S == U) {
    A--;
  } else {
    B--;
  }
  cout << A << " " << B << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int wa(int n){
    int sum=0;
    while (n>0)
    {
        sum+=n%10;
        n /=10;
    }
    return sum;
}
int main(){
    int N,A,B,ans;
    ans = 0;
    cin >> N >> A >> B;
    for (int i = 0; i < N+1; i++)
    {
        if (wa(i)>=A)
        {
            if (wa(i)<=B)
            {
                ans+=i;
            }
            
        }
        
    }
    cout << ans;
    

}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int a,b,h,m;
double ans,sz,fz,j;
int main()
{
	cin>>a>>b>>h>>m;
	sz=(60*h+m)*0.5;
	fz=6*m;
	j=abs(sz-fz);
	if(j>180)j=360-j;
	ans=cos(j*M_PI/180);
	printf("%.20f",sqrt(a*a+b*b-2*a*b*ans));
	return 0;
}

Measured memory_bytes: 4232
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
#define rep_r(i,s,n)for(int i = n-1;i>=s;i--)
#define rep_re(i,s,n)for(int i = n;i>=s;i--)
using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_N = 100001;
static const ll MAX_M = 100001;

int main() {
	ll m, d; cin >> m >> d;
	ll ans = 0;
	repe(i, 1, m) {
		repe(j, 1, d) {
			ll d10 = j / 10;
			ll d1 = j % 10;

			if (i == d10 * d1 && d1 >= 2 && d10 >= 2) {
				ans++;
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
  string s;
  cin >> s;
  for (int i=0; i<s.size(); i++){
    for (int j=i; j<s.size(); j++){
      string check = s.substr(0,i) + s.substr(j);
      if (check == "keyence") {
        cout << "YES" << endl;
        return 0;
      }
    }
  }
  cout << "NO" << endl;
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)(1e9+7)

ll moddiv(ll a,ll b){
    a %= MOD;
    b %= MOD;
    for(ll m=MOD-2;m>0;m/=2){
        if(m&1){
            a=a*b%MOD;
        }
        b=b*b%MOD;
    }
    return a;
}


ll Fa[202020];
void init(){
    ll i;
    Fa[0] = 1;
    fornum(i,0,201010){
        Fa[i + 1] = Fa[i] * (i + 1)%MOD;
    }
}




ll N;
vector<ll> abv[202020];
ll i, j, k;
pair<ll,ll> mk[202020];
ll anss[202020];
pair<ll,ll> dfs1(ll a,ll p){
    ll ret1 = 0;
    ll ret2 = 1;
    ll i;
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p)
            continue;
        auto r = dfs1(b, a);
        ret1 += r.first;
        (ret2 *= moddiv(r.second, Fa[r.first])) %= MOD;
    }
    (ret2 *= Fa[ret1]) %= MOD;
    
    //printf("%lld ", (ll)ret2);
    return mk[a] = {ret1 + 1, ret2};
}
void dfs2(ll a,ll p,ll n,ll c){
    //printf("%lld,%lld,%lld,%lld\n", a, p, n, c);
    ll i;
    (c *= moddiv(1, Fa[n]))%=MOD;
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p)
            continue;
        n += mk[b].first;
        (c *= moddiv(mk[b].second, Fa[mk[b].first])) %= MOD;
    }
    (anss[a] = Fa[n] * c) %= MOD;
    //printf("...%lld\n", c);
    
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p)
            continue;
        dfs2(b, a,
             N - mk[b].first,
             moddiv(c * Fa[n - mk[b].first] % MOD * Fa[mk[b].first], mk[b].second));
    }
}



int main(){
    init();
    scanf("%lld", &N);
    fornum(i,1,N){
        ll a, b;
        scanf("%lld%lld", &a, &b);
        abv[a].push_back(b);
        abv[b].push_back(a);
    }
    dfs1(1,0);
    dfs2(1, 0, 0, 1);
    fornum(i,0,N){
        printf("%lld\n", anss[i+1]);
    }

    return 0;
}

Measured memory_bytes: 21104
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

//--------------------------------------------

int q, od, a,b, bsum;
priority_queue<int> smalla;
int la;
priority_queue<int,vi,greater<int>> biga;
int ra;

void update(){
    if (smalla.empty()){
        smalla.push(a);
        return;
    } 
    auto thres = smalla.top();
    if ( a <= thres) {
        auto sm = smalla.top();
        la += (a <= sm ? sm - a : (a-sm) * smalla.size());
        
        smalla.push(a);

    } else {
        if (biga.empty()){
            biga.push(a);
        } else {
            auto bg = biga.top();
            ra += (bg <= a ? a - bg : (bg - a) * biga.size());

           biga.push(a);
        }
    }
    
    if (smalla.size() - 1 > biga.size() ){
        if (biga.empty()){ // la2, ba0
            biga.push(smalla.top());
            smalla.pop();
            la = 0;
            ra = 0;
        } else {
            auto sm = smalla.top();
            smalla.pop();
            auto bg = biga.top();
            auto sm2 = smalla.top();
            
            la -= (sm - sm2) * smalla.size();
            ra += (bg - sm) * biga.size();

            biga.push(sm);
        }
    }
    if (smalla.size() < biga.size()){
        auto bg = biga.top();
        biga.pop();
        auto sm = smalla.top();
        auto bg2 = biga.top();

        la += (bg - sm) * smalla.size();
        ra -= (bg2 - bg) * biga.size();

        smalla.push(bg);
    }
}

signed main(){
    I(q);
    REP(_,q){
        I(od);
        if (od == 1){
            I(a); I(b);
            update();
            bsum += b;
        } else {
            cout << smalla.top() << " ";
            int fx = bsum;
            fx += la + ra;
            if (!biga.empty()) fx += (biga.top() - smalla.top()) * biga.size();
            cout << fx << endl;
        }
    }
}

Measured memory_bytes: 3828
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    #while (len(q) != 0):
    while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

Measured memory_bytes: 95080
#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff first
#define ss second
//#define M 1000000007
#define MAXN 100100
using namespace std;
typedef pair<int,int> pii;
const int M = 1e15;
inline int mod(int n, int m){int ret = n%m; if(ret < 0) ret += m; return ret;}
int exp(int a,int b,int m){
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }    else return mod(k*k,m);
}
int n,m;
string s;

//inverte e faz guloso!
vector<int> res;
string t;

void solve(int x){
	if(x==0)return;
	for(int i=m;i>=1;i--){
		if(x-i>=0){
		  if(s[x-i]=='0'){
			  res.pb(i);
			  solve(x-i);
			  return;
		  }	
		}
		
	}
}


int32_t main(){
	fastio;

	cin>>n>>m;
	cin>>s;
	int big=0;
	for(int i=0;i<=n;){
		int atual = s[i]-'0';
		int ini = i;
		while(i<=n && s[i]-'0'==atual){
			i++;
		}
		if(atual==1)big = max(big,i-ini);
	}
	if(big>=m)return cout<<-1<<endl,0;
	//tenho q achar a menor resposta:
	solve(n);
	reverse(res.begin(),res.end());
	for(int i=0;i<(int)res.size();i++){
		cout<<res[i]<<" ";
	}
	cout<<endl;
}

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

#define ll long long int
using namespace std;
int main()
{
ll n;
cin>>n;
ll a,b;
cin>>a>>b;
ll arr[n];

for(ll i = 0;i<n;i++)
{
cin>>arr[i];
}
ll mx = 1e9;
 
ll mn = 1;
 
while(mn!= mx)
{
ll mid = (mn+mx)/2;
ll rem = mid;
ll b_cm = mid*b;
ll i;
for( i = 0;i<n;i++)
{
if(arr[i]> b_cm)
{
	ll req ;
	if((arr[i] - b_cm)%(a-b))
	req = ((arr[i] - b_cm)/(a-b)) +1;
	else 
	req = (arr[i] - b_cm)/(a-b);
if(req >rem )
break;
else rem -= req;
}
}
if(i==n)
mx = mid;
else 
mn = mid+1;
}
cout<<mn;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  vector<vector<pair<int, int>>> v(n);
  rep(i, n) {
    cin >> a[i];
    rep(j, a[i]) {
      int x, y;
      cin >> x >> y;
      x--;
      v[i].emplace_back(x, y);
    }
  }
  int ans = 0;
  rep(i, 1<<n) {
    bool flag = true;
    rep(j, n) {
      if (1<<j & i) {
        for (auto e : v[j]) {
          if (e.second ^ (i>>e.first & 1))
            flag = false;
        }
      }
    }
    if (flag)
      chmax(ans, __builtin_popcount(i));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;
const double pi = acos(-1.0);

int main() {
    int w, a, b; cin >> w >> a >> b;
    if(abs(a-b) <= w) cout << 0 << endl;
    else cout << abs(a-b) - w << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
  ldouble a, b, c;
  cin >> a >> b >> c;
  if(c-a-b > 2*sqrt(a*b)) cout << "Yes" <<endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    K, S = MI()
    ans = 0

    for x in range(0, K+1):
        for y in range(0, K+1):
            z = S - x - y
            if z >= 0 and z <= K:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 41192
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
ll p[15],c[15],g;
ll compute(ll val){
	ll i,don=0,res=0,val1,fl=0;
	rep(i,10){
		if(val&(1<<i)){
			don+=p[i]*100*(i+1);
			don+=c[i];
			res+=p[i];
		}
	}
	if(don>=g){
		return res;
	}
	fd(i,10,0){
		if(val&(1<<i)){
			continue;
		}
		val1=p[i];
		while(val1>1){
			don+=100*(i+1);
			res++;
			val1--;
			if(don>=g){
				fl=1;
				break;
			}
		}
		if(fl){
			break;
		}
	}
	if(don<g){
		return inf;
	}
	return res;
}
int main(){
	std::ios::sync_with_stdio(false);
	ll d,ans=inf,val,i;
	cin>>d>>g;
	rep(i,d){
		cin>>p[i]>>c[i];
	}	
	val=(1<<d);
	rep(i,val){
		ans=min(ans,compute(i));
		//cout<<comput3(i)<<endl;
	}
	cout<<ans<<endl;
} 
	

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#include<limits.h>
#define SIZE 100002
typedef long long ll;
ll main(){
    ll table[SIZE]={0},sum=0;
    ll N;
    scanf("%lld",&N);
    ll A[SIZE];
    for(ll i=0;i<N;i++){
        scanf("%lld",A+i);
        table[A[i]]++;
        sum += A[i];
    }
    ll Q;
    scanf("%lld",&Q);
    ll B[SIZE],C[SIZE];
    for(ll i=0;i<Q;i++)
        scanf("%lld %lld",B+i,C+i);
    for(ll i=0;i<Q;i++){
        sum += table[B[i]] * (C[i] - B[i]);
        printf("%lld\n",sum);
        table[C[i]] += table[B[i]];
        table[B[i]] = 0;
    }
}


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

using CP = complex<long double>;
#define X real()
#define Y imag()
const long double PI = acos(-1.0L);
const long double EPS = 1e-10;
// conj(x) : complex conjugate,(0,1)->(0,-1)
// abs(x) : dist between(0,0) and x
// norm(x) : abs(x) * abs(x)
// arg(x) : argment

// dot(a,b) = |a||b|cos x
long double dot(CP a, CP b) { return (a * conj(b)).X; }
// cross(a,b) : area of parallelogram
long double cross(CP a, CP b) { return (a * conj(b)).Y; }
long double corner(CP a, CP b) {
  //[0,pi]
  return acos(dot(a, b) / (abs(a) * abs(b)));
}
CP projection(CP p, CP s, CP t) {
  CP base = t - s;
  long double r = dot(p - s, base) / norm(base);
  return s + base * r;
}
CP reflection(CP p, CP s, CP t) {
  CP tmp = (projection(p, s, t) - p);
  tmp *= 2;
  return p + tmp;
}

CP intersection(CP a, CP b, CP c, CP d) {
  return a + (b - a) * (cross(d - c, c - a) /
                        cross(d - c, b - a));
}

bool on_seg(CP a, CP b, CP p) {
  // if not use end point, dot(a - p, b - p) < 0
  return abs(cross(a - p, b - p)) <= 1e-10 &&
         dot(a - p, b - p) <= 0;
}

// crossing lines? (a,b) and (c,d)
bool iscross(CP a, CP b, CP c, CP d) {
  // parallel
  if(abs(cross(a - b, c - d)) <= 1e-10) {
    return on_seg(a, b, c) || on_seg(a, b, d) ||
           on_seg(c, d, a) || on_seg(c, d, b);
  }
  CP isp = intersection(a, b, c, d);
  return on_seg(a, b, isp) && on_seg(c, d, isp);
}

long double distLP(CP a, CP b, CP p) {
  return abs(cross(b - a, p - a) / abs(b - a));
}

// segmentver.
long double distSP(CP a, CP b, CP p) {
  if(dot(b - a, p - a) < 0) return abs(p - a);
  if(dot(a - b, p - b) < 0) return abs(p - b);
  return distLP(a, b, p);
}

// segment and segment
long double distSS(CP a, CP b, CP c, CP d) {
  long double res = 1e18;
  res = min(res, distSP(a, b, c));
  res = min(res, distSP(a, b, d));
  res = min(res, distSP(c, d, a));
  res = min(res, distSP(c, d, b));
  return res;
}

struct convex_hull {
  vector<CP> ch;
  int psize;
  convex_hull() {}
  convex_hull(vector<CP> &ps) { calculation(ps); }
  void calculation(vector<CP> &ps) {
    auto lmd = [&](const CP &l, const CP &r) {
      if(l.X != r.X) return l.X < r.X;
      return l.Y < r.Y;
    };
    psize = ps.size();
    sort(ps.begin(), ps.end(), lmd);
    int k = 0;
    ch.resize(psize * 2);
    for(int i = 0; i < psize; ++i) {
      while(k > 1 && cross(ch[k - 1] - ch[k - 2],
                           ps[i] - ch[k - 1]) <= 0)
        --k;
      ch[k++] = ps[i];
    }
    for(int i = psize - 2, t = k; i >= 0; --i) {
      while(k > t && cross(ch[k - 1] - ch[k - 2],
                           ps[i] - ch[k - 1]) <= 0)
        --k;
      ch[k++] = ps[i];
    }
    ch.resize(k - 1);
    psize = ch.size();
  }
};

CP s;

int main() {
  cout << fixed << setprecision(10);
  long double a, b, c, d;
  cin >> a >> b >> c >> d;
  s = CP(a, b) - CP(c, d);
  cout << abs(s) << endl;
  return 0;
}


Measured memory_bytes: 3312
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

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

	int N, P;
	cin >> N >> P;

	string S;
	cin >> S;

	long long result = 0;
	if (P == 2 || P == 5)
	{
		for (int i = 0; i < N; i++)
		{
			if ((S[i] - '0') % P == 0)
			{
				result += (i + 1);
			}
		}
	}
	else
	{
		vector<int> base(N, 1);
		for (int i = N - 1; i >= 1; i--)
		{
			base[i - 1] = (base[i] * 10) % P;
		}

		vector<int> mod_count(P, 0);
		mod_count[0] = 1;

		int mod = 0;
		for (int i = 0; i < N; i++)
		{
			mod = (mod + (((S[i] - '0') % P) * base[i]) % P) % P;
			mod_count[mod]++;
		}

		for (long long val : mod_count)
		{
			result += (val * (val - 1)) / 2;
		}
	}

	cout << result;

	return 0;
}

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

const int INF=123456789;

typedef pair<int,int> P;

char maze[101][101];
int H,W;

int d[101][101];


int main(){
  cin>>H>>W;
  for(int i=0;i<H;i++) for(int j=0;j<W;j++){
    cin>>maze[i][j];
  }
  /*
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
    cout<<maze[i][j]<<" ";
  }
  cout<<endl;
}
*/
  for(int i=0;i<H;i++) {
    for(int j=0;j<W;j++){
       d[i][j]=INF;
     }
   }

   if(maze[0][0]=='#')d[0][0]=10000;
   else d[0][0]=0;

   for(int i=0;i<H-1;i++){
       if(maze[i+1][0]=='#') {
         if(maze[i][0]=='#') d[i+1][0]=d[i][0];
         else d[i+1][0]=d[i][0]+10000;
       }
       else d[i+1][0]=d[i][0];
     }

     for(int j=0;j<W-1;j++){
       if(maze[0][j+1]=='#') {
        if(maze[0][j]=='#') d[0][j+1]=d[0][j];
        else d[0][j+1]=d[0][j]+10000;
       }
       else d[0][j+1]=d[0][j];
     }

   for(int i=0;i<H-1;i++){
     for(int j=0;j<W-1;j++){

       if(maze[i+1][j+1]=='#'){
         if(maze[i+1][j]=='#')d[i+1][j+1] = min(d[i+1][j+1],d[i+1][j]);
         if(maze[i][j+1]=='#')d[i+1][j+1] = min(d[i+1][j+1],d[i][j+1]);
         if(maze[i+1][j]=='.'||maze[i][j+1]=='.') d[i+1][j+1] = min(d[i+1][j+1],min(d[i+1][j],d[i][j+1])+10000);
       }
       else{
         d[i+1][j+1] = min(d[i+1][j],d[i][j+1]);
       }
     }
   }
   /*
   for(int i=0;i<H;i++){
     for(int j=0;j<W;j++){
     cout<<d[i][j]/10000<<" ";
   }
   cout<<endl;
 }
*/
  cout<<d[H-1][W-1]/10000<<endl;
}


Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        int a=sc.nextInt();
        int m=sc.nextInt();
        int n[]=new int[m];
        long all=0;
        for(int i=0;i<m;i++) {
            n[i] = sc.nextInt();
            all += n[i];
        }
        if(all>=a)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 50208
unittest
{
	assert( [ "3 2", "1 2", "2 3" ].parse.expand.solve == "POSSIBLE" );
	assert( [ "4 3", "1 2", "2 3", "3 4" ].parse.expand.solve == "IMPOSSIBLE" );
	assert( [ "100000 1", "1 99999" ].parse.expand.solve == "IMPOSSIBLE" );
	assert( [ "5 5", "1 3", "4 5", "2 3", "2 4", "1 4" ].parse.expand.solve == "POSSIBLE" );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nm = input.front.split.to!( long[] );
	auto abs = new long[ 2 ][ nm[ 1 ] ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
	}
	return tuple( nm[ 0 ], abs );
}

auto solve( long n, long[ 2 ][] abs )
{
	// 島1から他の島へ行く定期船を調べる
	auto s1 = abs.filter!( ( ab ) => ab[ 0 ] == 1 ).map!( ( ab ) => ab[ 1 ] ).array;
	s1.sort();
	
	// 他の島から島Nへ行く定期船を調べる
	auto s2 = abs.filter!( ( ab ) => ab[ 1 ] == n ).map!( ( ab ) => ab[ 0 ] ).array;
	s2.sort();
	
	// 島1と島Nの両方から行ける島を調べる
	while( !s1.empty && !s2.empty )
	{
		if( s1.front == s2.front ) return "POSSIBLE";
		
		if( s1.front < s2.front ) s1.popFront;
		else                      s2.popFront;
	}
	
	return "IMPOSSIBLE";
}


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

int main(){
    
    string s;
    cin >> s;
    int n = s.size();
    int a = n,b = -1;
    rep(i,n){
        if(s[i] == 'A')a = min(a,i);
        if(s[i] == 'Z')b = max(b,i);
    }
    cout << b-a+1 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; ++i)
typedef long long ll;
const int INF = 1 << 30;
using namespace std;

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

  int n; cin >> n;

  if(n == 1) {
    cout << 1 << endl;
    return 0;
  }

  vector<pair<ll, ll> > xy(n);
  rep(i, n) {
    ll x, y;
    cin >> x >> y;
    xy[i].first = x;  xy[i].second = y;
  }

  map<pair<ll, ll>, int> mp;
  // case n != 1
  rep(i, n) rep(j, n) {
    // (p, q) != (0, 0)
    if(i == j) continue;
    ll p = xy[i].first - xy[j].first;
    ll q = xy[i].second - xy[j].second;
    // backet
    mp[make_pair(p, q)]++;
  }

  int ans = INF;
  for(auto elem : mp) {
    ans = min(ans, n-elem.second);
  }
  cout << ans << '\n';
  return 0;
}


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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 10;

int dp[MAX];
vector<int> nums;

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

  for (int i = 6; i < MAX; i *= 6) nums.push_back(i);
  for (int i = 9; i < MAX; i *= 9) nums.push_back(i);

  // 初期化
  for (int i = 1; i <= N; i++) dp[i] = i;

  // 動的計画法
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < nums.size(); j++) {
      if (i - nums[j] < 0) continue;
      dp[i] = min(dp[i], dp[i-nums[j]] + 1);
    }
  }

  cout << dp[N] << endl;
  return 0;
}


Measured memory_bytes: 640