akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	private Scanner sc;
	
	public static void main(String[] args) {
		new Main();
	}
	
	public Main() {
		sc = new Scanner(System.in);
		
		while (sc.hasNextLine() == true) {
			int sum = Integer.parseInt(sc.nextLine());
			
			ArrayList<Integer> list = new ArrayList<Integer>();
			
			int n = 1;
			
			while (sum > 0) {
				int mod = sum % 2;
				if (mod == 1) {
					list.add(n);
				}
				
				sum = sum / 2;
				n = n * 2;
			}
			
			StringBuilder sb = new StringBuilder();
			sb.append(list.get(0));
			for (int i = 1; i < list.size(); i++) {
				sb.append(" " + list.get(i));
			}
			System.out.println(sb.toString());
		}
	}
}

Measured memory_bytes: 25956
#include <algorithm>
#include <map>
#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <iterator>
#include <array>
#include <iomanip>
typedef long long int ll;
using namespace std;
#define maxN 200005
#define mod 1000000007
#define pi 3.14159265358979323846264338327950

void solve()
{
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double angle = (30 * h - 5.5 * m)*pi / 180.0;
    double ans = a * a + b * b - 2 * a * b * cosl(angle);
    cout << fixed << setprecision(20) << sqrt(ans) << endl;
}

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

Measured memory_bytes: 4084
/*Author - Shubham Gupta (@shubham107)*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;      typedef vector<int> vi;
typedef vector<vl> vvl;     typedef vector<vi> vvi;
typedef pair<ll, ll> pll;   typedef pair<int, int> pii;
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define INF ll(1e18)
#ifdef SHUBHAM107
#include "../trace.h"
#else
#define trace(args...)
#endif
void solve() {
    int h, w, k;
    cin >> h >> w >> k;
    vvi mat(h, vi(w, 0));
    forn(i, h) forn(j, w) {
        char c;
        cin >> c;
        if(c == '#') mat[i][j] = 1;
    }

    auto f = [&](int row, int col) {
        int cnt = 0;
        forn(i, h) forn(j, w) {
            if((row >> i & 1) || (col >> j & 1))
                continue;
            cnt += mat[i][j];
        }
        return cnt == k;
    };
    int ans = 0;
    for(int mask1 = 0; mask1 < (1 << h); mask1++) {
        for(int mask2 = 0; mask2 < (1 << w); mask2++) {
            ans += f(mask1, mask2);
        }
    }
    cout << ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef SHUBHAM107
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("err.txt", "w", stderr);
#endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll n, m;
        in >> n >> m;
        ll ans = m * 1900 + (n - m) * 100;
        for (int i = 0; i < m; i++) {
            ans *= 2;
        }
        out << ans << '\n';
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 256
/*
 * じょえチャンネル
 * 高評価・チャンネル登録よろしくおねがいします！
 * https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
 */
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)
template<class T> inline void chmin(T &a, T b) {
	a = min(a, b);
}
template<class T> inline void chmax(T &a, T b) {
	a = max(a, b);
}

int n,p;
string s;
int a[200005];
int cnt[10005];
int mod_pow(int x, int y, int m = mod) {
	int res = 1;
	x %= m;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
signed main(){
	cin>>n>>p>>s;
	rep(i,n)a[i]=s[i]-'0';
	cnt[0]=1;
	if(p<=5){
		int dp[200005][5];memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		int ans=0,now=0;
		rep(i,n){
			now=now*10+a[i];
			now%=p;
			ans+=dp[i][now];
			dp[i][now]++;
			rep(j,5)dp[i+1][j*10%p]+=dp[i][j];
		}
		cout<<ans<<endl;return 0;
	}
	int now=0,ans=0,now2=1;
	rep(i,n){
		now=now*10+a[i];
		now%=p;
		ans+=cnt[now*mod_pow(now2,p-2,p)%p];
		cnt[now*mod_pow(now2,p-2,p)%p]++;
		now2=now2*10%p;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 9988
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin>>n;
    int A[100]{};
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
    }
    for(int i=0;i<n;i++)
    {
        int v{};
        v=A[i];
        int j;
        j=i-1;
        while(A[j]>v&&j>=0)
        {
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=v;
        cout<<A[0];
        for(int t=1;t<n;t++)cout<<" "<<A[t];
        cout<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 3096
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 14, 2020 12:42:18 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  B = list(map(int, input().split()))

  A = [0]*(N)
  A[0] = B[0]
  A[1] = B[0]
  for i in range(1, N-1):
    if A[i] > B[i]:
      A[i] = B[i]
    A[i+1] = B[i]

  # print(A)
  print(sum(A))


if(__name__ == '__main__'):
  main()


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

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

const long long MOD = 1000000007;

int main(){
  int a,b;
  cin>>a>>b;
  if(a>=13) cout<<b<<endl;
  else if(a>=6) cout<<b/2<<endl;
  else cout<<0<<endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from math import sqrt

def main():
    a, b, c = list(map(int, input().strip().split()))
    if c - a - b > 0 and 4 * a * b < (c - a - b) ** 2:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
using namespace std;
vector<int>a;
int main() {
	int t,n;
	cin >> t;
	n = t;
	while (n--)
	{
		int temp;
		cin >> temp;
		a.push_back(temp);
	}
	cin >> n;
	while (n--)
	{
		int begin, m, end;//开始，e-m位移 结束
		cin >> begin >> m >> end;
		swap_ranges(a.begin() + begin, a.begin() + m, a.begin() + end);
	}
	for (int i = 0; i < t; i++)
	{
		if (i != 0)
		{
			cout << " ";
		}
		cout << a[i];
	}
	cout << endl;
}




Measured memory_bytes: 3156
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

vector<ll> G[MAX];
ll n,m,s,t;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    rep(i,m){
        ll S,T;
        cin>>S>>T;
        S--;T--;
        G[S].pb(T);
    }
    cin>>s>>t;
    s--;t--;
    vector<vii>  dp(3,vii(n,-1));
    queue<pii> que;
    dp[0][s]=0;
    que.push(pii(0,s));
    while(!que.empty()){
        int d,v;
        tie(d,v)=que.front();
        que.pop();
        int nd=(d+1)%3;
        for(ll u:G[v]){
            // dp[nd][u]!=-1 then continue
            if(~dp[nd][u]) continue;
            dp[nd][u]=dp[d][v]+1;
            que.emplace(nd,u);
        }
    }
    if(~dp[0][t]) dp[0][t]/=3;
    cout<<dp[0][t]<<endl;
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
            int num = scn.nextInt();
            int arr[] = new int[num];
            for(int i = 0 ; i < num;i++){
                arr[i]= scn.nextInt();
            }
//        int num = 6;
//        int arr[] = {30, 10, 60, 10, 60, 50};

        int dp[] = new int[num];
        Arrays.fill(dp, (int) 2e9);
        System.out.println(minCostJump(arr, dp));


    }

    private static int minCostJump(int[] arr, int[] dp) {
        dp[0]=0;
        int n  = arr.length;
        for(int i=0;i<n;i++) {
            for (int j = 1; j <= 2; j++) {
                if (i + j < n)
                    dp[i + j] = Math.min(dp[i + j], (dp[i] + Math.abs(arr[i + j] - arr[i])));
            }
        } return dp[arr.length-1];
    }
}

Measured memory_bytes: 48040
#include <iostream>
#include <vector>
using namespace std;
int n,q;
int a,b;
vector<int> v[200001];
int ans[200001];
bool arrive[200001];
int p,x;

void dfs(int node,int num){
    ans[node]+=num;
    arrive[node]=true;
    for(int i=0;i<v[node].size();i++){
        if(!arrive[v[node][i]])dfs(v[node][i],ans[node]);
    }
    return;
}

int main(){
    cin>>n>>q;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=0;i<q;i++){
        cin>>p>>x;
        ans[p]+=x;
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        if(i-1)cout<<" ";
        cout<<ans[i];
    }
}

Measured memory_bytes: 23680
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int ans;
  if(a>=b) ans+=b;
  else ans+=a;
  if(c>=d) ans+=d;
  else ans+=c;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
a = [input() for i in range(2)]

text = a[0]
iter = int(a[1])

text_list = list(text)
ren = []
start = text_list[0]
a = 0
for i in range(1,len(text_list)):
  if text_list[i] == start:
    a += 1
    if i == len(text_list)-1:
      ren.append(a)
  else:
    start = text_list[i]
    ren.append(a)
    a = 0

for i in range(len(ren)):
  ren[i] += 1

if ren == []:
  ren = [1]
  
ans = 0
if len(ren) == 1:
  ans = ren[0] * iter // 2
elif text_list[0] == text_list[-1]:
  if ren[0] % 2 == 1 and ren[-1] % 2 == 1:
    for r in ren:
      ans += (r//2)
    ans *= iter
    ans += iter-1
  else:
    for r in ren:
      ans += (r//2)
    ans *= iter    
else:
  for r in ren:
    ans += (r//2)
  ans *= iter

print(ans)
    


Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> a(m);
    cin >> a;
    int s = accumulate(all(a), 0);
    if (s > n)
        cout << "-1";
    else
        cout << n - s;
    return 0;
}

Measured memory_bytes: 3668
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
	int n, m;
	cin >> n >> m;
	int sum = 0;
	for (int i = 0; i < m; i++){
		int a;
		cin >> a;
		sum += a;
	}
	if (n >= sum) cout << n-sum << endl;
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 3640
using System;

class ABC_139_A
{
    static void Main(string[] args)
    {
        string S = Console.ReadLine();
        string T = Console.ReadLine();

        int count = 0;
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] == T[i]) count++;
        }

        Console.WriteLine(count);
    }
}


Measured memory_bytes: 13140
n=int(input())
l=[]
for i in range(n):
    l.append(str(input()))

C1=l.count("AC")
C2=l.count("WA")
C3=l.count("TLE")
C4=l.count("RE")

print("AC x " + str(C1))
print("WA x " + str(C2))
print("TLE x " + str(C3))
print("RE x " + str(C4))


Measured memory_bytes: 16112
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def comb(n, k):
    if n == 0 or k == 0:
        return 1
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def rec(S, K):
    #print(S, K)
    N = len(S)
    if N == 0 or K == 0 or N < K:
        return 0
    h = int(S[0])
    c = comb(N - 1, K - 1)
    ret = (9 - h) * c * (9 ** (K - 1))
    if S[0] == '0':
        ret += rec(S[1:], K)
    else:
        ret += rec(S[1:], K - 1)
    #print(S, K, ret)
    return ret

def solve(S: str, K: int):
    N = len(S)
    if N < K:
        print(0)
        return 0
    ret = comb(N, K) * (9 ** K)
    ret -= rec(S, K)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = str(next(tokens)) 
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
def main():
  N,M=map(int,input().split())
  A=[0]*M
  import heapq
  import collections
  from itertools import permutations
  table=collections.defaultdict(list)
  AC=[[0,0] for i in range(M)]
  C=[set() for i in range(M)]
  for i in range(M):
    a,b=map(int,input().split())
    AC[i][0]=a
    tmp=set(map(int,input().split()))
    for x in tmp:
      AC[i][1] |= 1<<(x-1)
  dp=[10**9]*(2**N)
  dp[0]=0

  for i in range(1,2**N):
    k=0
    s=set()
    for j in range(1,i):
      if i & j == j:
        dp[i]=min(dp[i],dp[j]+dp[i^j])
    for a,c in AC:
      if c&i == i:
        dp[i]=min(dp[i],a)
    #print(dp[i],bin(i))

  if dp[-1]==10**9:
    print(-1)
  else:
    print(dp[-1])
main()

Measured memory_bytes: 3692
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadIntArray(3);

            if (a.Sum() >= 22)
            {
                WriteLine("bust");
            }
            else WriteLine("win");
        }
    }

    public static class Extensions
    {
        
    }


    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 13396
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
using P = pair<int, int>;
using PP=pair<P, int>;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) {
			if (mod <= ans * x) ans = ans * x % mod;
			else ans *= x;
		}
		if (mod <= x * x) x = x * x % mod;
		else x *= x;
		n >>= 1;
	}
	return ans;
}

int fact_memo[114514];
int fact(int n) {
	int ans = 1;
	if (fact_memo[n]) return fact_memo[n];
	rep(i, n) {
		ans *= (i + 1);
		if (mod <= ans) ans %= mod;
		fact_memo[i + 1] = ans;
	}
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) + mod) % mod;
}

int perm(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod + mod) % mod;
}

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

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

int n;
int a[200010], ans[200010];
int cnt1;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	for (int i = n / 2; i < n; i++) {
		if (a[i]) {
			ans[i]++;
			cnt1++;
		}
	}
	Rep(i, n / 2 - 1) {
		int cnt = 0;
		for (int j = 2 * (i+1)-1; j < n; j += (i + 1)) {
			cnt += ans[j];
		}
		if (a[i] != cnt % 2) {
			ans[i]++;
			cnt1++;
		}
	}
	cout << cnt1 << endl;
	rep(i, n) {
		if (ans[i]) {
			cout << i+1<< endl;
		}
	}
}


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;

void test_case(){
    
}

int main() {
    fastio
    int N, R;
    cin >> N >> R;
	
	if(N>= 10)
		cout<<R<<endl;
	else{
		cout<<R+100*abs(10-N)<<endl;
		}
	
	return 0;
}






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

using namespace std;

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

  int ans = 0;
  for(int i = 0; i < n; i++){
    if(s.substr(i, 3) == "ABC"){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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;
}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    int a, b , c, k;
    cin >> a >> b >> c >> k;

    assert(a+b+c >= k);

    ll ans = 0;

    ans += min(k, a);

    if (k > a+b) {
        ans -= k-(a+b);
    }

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


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

int main() {
	int n;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++)cin >> a.at(i);
	vector<int>b(n);
	for (int i = 0; i < n; i++)cin >> b.at(i);
	vector<int>c(n-1);
	for (int i = 0; i < n-1; i++)cin >> c.at(i);
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ans += b.at(a.at(i) - 1);
		if (i != 0) {
			if (a.at(i) - a.at(i - 1) == 1)ans += c.at(a.at(i - 1) - 1);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> vec(N);
  int64_t sum = 0;
  for(int i=0; i<N; i++){
    cin >> vec[i];
    sum += vec[i];
  }
  vector<int64_t> d(N);
  for(int i=0; i<N-1; i++){
    d[i] = vec[i+1] - vec[i];
  }
  d[N-1] = vec[0] - vec[N-1];
  
  bool flag = true;
  int64_t cnt = sum / (N*(N+1)/2);
  if(sum % (N*(N+1)/2) != 0){
    flag = false;
  }
  
  int64_t num = 0;
  for(int i=0; i<N; i++){
    int64_t C = 0;
    while(cnt - C != d[i]){
      if(d[i] > cnt){
        flag = false;
        break;
      }
      d[i] += N-1;
      C++;
      num++;
    }
  }
  
  
  if(flag && num == cnt){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
      
  
}

Measured memory_bytes: 4808
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<map>
#include<list>

using namespace std;

#define in(s) cin >> s
#define out(s) cout << s << endl
#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define MOD 1000000007

#define IMIN INT_MIN;
#define IMAX INT_MAX;


int main(){
    int N, M;
    in(N); in(M);
    vector<int> H(N);
    rep(i, N) in(H[i]);
    vector<int> A(M), B(M);
    vector<bool> good(N, true);
    rep(i, M) {
        in(A[i]);
        in(B[i]);
        if (H[A[i]-1] <= H[B[i]-1]) good[A[i]-1] = false;
        if (H[B[i]-1] <= H[A[i]-1]) good[B[i]-1] = false;
    }
    int cnt = 0;
    rep(i, N) {
        if (good[i]) cnt++;
    }

    out(cnt);
	return 0;
}


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

const int M = 1e9+7;

int mul(int a, int b){
    return (ll)a*b%M;
}

int add(int a, int b){
    return (a+b)%M;
}

int p(int a,int b){
    ll res = 1;
    while(b>0){
        if(b%2) res = mul(res,a);
        a = mul(a,a);
        b/=2;
    }
    return res%M;
}

int self_inv(int a){
    return p(a,M-2);
}

int sub(int a, int b){
    return (a%M - b%M + M)%M;
}

int nck(int n, int k){
    if(n<=0 || k<=0) return 1;
    int res = 1;
    for(int i = n; i>n-k; i--){
        res = mul(res,i);
    }
    int kfact = 1;
    for(int i = k ; i>0; i--){
        kfact = mul(kfact,i);
    }
    return mul(res,self_inv(kfact));
}

int main(){
    ll n,a,b;cin>>n>>a>>b;
    
    ll ans = p(2,n)-1;
    ans = sub(ans,nck(n,a));
    ans = sub(ans,nck(n,b));
    cout<<ans;

}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    auto N = readln.chomp.map!(ch => (ch - '0').to!int).retro.array;
    N ~= 0;

    auto L = N.length.to!int;
    auto dp = new int[][](L + 1, 2);
    fillAll(dp, inf);
    dp[0][0] = 0;

    foreach (i ; 0 .. L) {
        foreach (j ; 0 .. 2) {
            foreach (d ; 0 .. 10) {
                int x = N[i] + j;
                if (x <= d) { // 繰り下がりが発生しない
                    chmin(dp[i + 1][0], dp[i][j] + d + d - x);
                }
                else { // x > d, 繰り下がりが発生する
                    chmin(dp[i + 1][1], dp[i][j] + d + 10 + d - x);
                }
            }
        }
    }

    auto ans = dp[L][0];
    writeln(ans);
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 48680
#include<stdio.h>
int main()
{
	int a,b,c;
	while(~scanf("%d%d%d",&a,&b,&c))
	{
		if(a==5&&b==5&&c==7||a==5&&b==7&&c==5||a==7&&b==5&&c==5)
		   printf("YES\n");
		else printf("NO\n");   
	}
}//

Measured memory_bytes: 128
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      long n = sc.nextLong();
      long p = sc.nextLong();
      long max = 1;
      for(long i = 1;i <= Math.sqrt(p);i++){
        long q = (long)Math.pow(i,n);
        if(p%q==0)max = i;
      }
      if(n==1)max = p;
      System.out.println(max);
    }
}


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

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)

using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    int len_max = 0;
    FOR(dist, 1, N) {
        int len = 0;
        REP(i, N - dist + 1) {
            int j = i + dist;
            if (j == N || S[i] != S[j]) {
                len_max = max(len_max, min(len, dist));
                len = 0;
            } else {
                ++len;
            }
        }
    }
    cout << len_max << endl;
    return 0;
}

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

int main(){
	int n, d;
  	scanf("%d%d", &n, &d);
  	vector<vector<int>> points(n, vector<int>(d));
  	for(auto &vec : points){
    	for(auto &coord : vec){
        	cin >> coord;
        }
    }
  	auto sqr = [](int num){
    	return num * num;
    };
  	auto dist = [&](const vector<int> &v1, const vector<int> &v2){
      	int result = 0;
    	for(int i = 0; i < v1.size(); ++i){
        	result += sqr(v1[i] - v2[i]);
        }
      return result;
    };
  	
  	auto check = [&](int num){
      	int val = sqrt(num) + 1;
      	return sqr(val) == num || sqr(val - 1) == num;
    };
  
  	int ans = 0;
  	for(int i = 0; i < n; ++i){
    	for(int j = i + 1; j < n; ++j){
        	if (check(dist(points[i], points[j]))) ++ans;
        }
    }
	printf("%d", ans);
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N = int(input())
S = input()
black = 0
white = 0
l = [] # 

for s in S:
    if s == "#":
        black += 1
    else:
        white += 1

if white == 0:
    print(0)
    
else:
    leftBlack = 0
    rightWhite = white
    l.append(leftBlack + rightWhite)
    for s in S:
        if s == "#":
            leftBlack += 1
        else:
            rightWhite -= 1
            
        l.append(leftBlack + rightWhite)
        
    print(min(l))


Measured memory_bytes: 55388
using System;
public class c
{
  public static void Main()
  {
    int n = int.Parse(Console.ReadLine());
    string[] s=Console.ReadLine().Split(' ');
    int sum=0;
    for(int i=0;i<n;i++)
    {
      sum+=int.Parse(s[i]);
    }
  if(sum%2==0)Console.WriteLine("YES");
  else Console.WriteLine("NO");
  }
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N, M;
  cin >> N >> M;

  vector<vector<int>> G(N+M);

  for(int i = 0; i < N; i++){
    int K;
    cin >> K;
    int l;
    for(int k = 0; k < K; k++){
      cin >> l;
      l--;
      G[i].push_back(N+l);
      G[N+l].push_back(i);
    }
  }

  vector<int> visited(N+M);

  for(int i = 0; i < N+M; i++){
    visited[i] = -1;
  }

  queue<int> q;
  q.push(0);
  visited[0] = 1;

  while(!q.empty()){
    int v = q.front();
    q.pop();

    for(int nv : G[v]){
      if(visited[nv] == 1) continue;

      visited[nv] = 1;
      q.push(nv);
    }
  }

  bool ans = true;

  for(int i = 0; i < N; i++){
    if(visited[i] == -1){
      ans = false;
      break;
    }
  }

  if(ans){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  


  return 0;
}


Measured memory_bytes: 9720
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

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 (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


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

    if (n==m) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;

const int N = 3005;
const i64 MOD = 1000000007;

int v[N], st[N], dr[N];
i64 dp[N][N];

vector<pii> ivs;
string str;
int n, m, one;

int main() {
#ifdef HOME
	freopen("arc65d.in", "r", stdin);
	freopen("arc65d.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	cin >> str;
	ivs.resize(m);
	for (auto &i: ivs)
		cin >> i.x >> i.y;

	for (int i = 0; i < n; ++i) if (str[i] == '1')
		v[i + 1] = ++one;

	for (int i = 0; i < m; ++i)
		stable_partition(v + ivs[i].x, v + ivs[i].y + 1, [&](int x) { return x; });
	for (int i = 1; i <= n; ++i) if (v[i])
		st[v[i]] = i;

	memset(v, 0x00, sizeof v);
	one = 0;

	for (int i = 0; i < n; ++i) if (str[i] == '1')
		v[i + 1] = ++one;

	for (int i = 0; i < m; ++i)
		stable_partition(v + ivs[i].x, v + ivs[i].y + 1, [&](int x) { return !x; });
	for (int i = 1; i <= n; ++i) if (v[i])
		dr[v[i]] = i;

	for (int i = 0; i <= n; ++i)
		dp[i][0] = 1;

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= one; ++j) {
			dp[i][j]+= dp[i - 1][j];

			if (st[j] <= i && i <= dr[j]) 
				dp[i][j]+= dp[i - 1][j - 1];

			if (dp[i][j] >= MOD)
				dp[i][j]-= MOD; }

	cout << dp[n][one] % MOD << endl;

	return 0; }


Measured memory_bytes: 69888
R, G, B, N = map(int, input().split())

r, g, b = int(N // R), int(N // G), int(N // B)

ans = 0
for i in range(r + 1):
    if i * R > N:
        break
    for j in range(g + 1):
        if (N - (i * R + j * G)) % B == 0 and (N - (i * R + j * G)) >= 0:
            ans += 1
print(ans)


Measured memory_bytes: 40940
/*input
100000 100000
*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>*/
using namespace std;
/*using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;*/
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long ll;
typedef long double ld;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
ll dp[maxn];
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,k;
    cin>>n>>k;
    ll ans=0;
    for(ll z=k;z>=1;z--){
        ll tmp=mypow((k/z),n);
        for(int j=z*2;j<=k;j+=z){
            tmp=(tmp-dp[j]+MOD)%MOD;
        }
        dp[z]=tmp;
        ans+=mult(tmp,z);
        ans%=MOD;
    }
    cout<<ans;
}

Measured memory_bytes: 4428
#include <algorithm>
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define mod (int)(1e9 + 21)
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define int long long
#define ll long long 
#define pb emplace_back
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define in(x) scanf("%intd", &x)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxheap priority_queue<int>
#define minheap priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define fi first
#define se second
#define kitna se
#define endl "\n"
#define pi pair<int, int>
#define LL long long 
const int MAXN = (int)((1e5) + 10);
int gcd(int a,int b) { if (a == 0) return b; return gcd(b%a, a);}
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a<b) return a; else return b;}  
bool isPrime(int N){ for(int i=2;i*i<=N;++i){if(N%i==0) return false;}return true;}
int cbrt(int x){ int lo=1,hi=min(2000000ll,x);while(hi-lo>1){int mid=(lo+hi)/2;if(mid*mid*mid<x){lo=mid;}else hi=mid;}if(hi*hi*hi<=x) return hi;else return lo;} 
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int nax =  (int)(1*1e5+10);
 
// int SPF[N+5];
 
// void SOF()
// {
//     SPF[1] = 1;
//     for (int i=2; i<N; i++)
//         SPF[i] = i;
//     for (int i=4; i<N; i+=2)
//         SPF[i] = 2;
 
//     for (int i=3; i*i<N; i++)
//         {
//         if (SPF[i] == i)
//             {
//             for (int kon=i*i; kon<N; kon+=i)
//                 if (SPF[kon]==kon)
//                    SPF[kon] = i;
//             }
//         }
// }
int a[nax];
int n; 
int dp[nax]; 
int k;
int func(int ind)
{
	if(ind==(n-1))
		return 0;
	else if(dp[ind]!=-1) return dp[ind];
	else
	{
		int ans = 1e9+5; 
		for(int i = 1;i<=k;i++)
		{
			if(ind+i<n)
				ans = min(ans,abs(a[ind+i]-a[ind]) + func(ind+i));
 
		}
		return dp[ind] = ans; 
	}
 
}
 
 
 
 
 
signed main(){
 
int t=1; 
//cin >> t;
// string s; 
// getline(cin,s);
 
while(t--)
{
    cin >> n >> k;
    for0(i,n) cin >> a[i]; 	
    ini(dp,-1); 
    cout << func(0); 
 
}
 
rr;
}

Measured memory_bytes: 11328
N = int(input())
A = list(map(int,input().split()))

X = sum(A)
Y = 0
MIN = 10**18
for i,a in enumerate(A):
    if i < N-1:
        X -= a
        Y += a
        tmp = abs(X-Y)
        if tmp < MIN:
            MIN = tmp
    
print(MIN)

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int X,Y,Z;
  cin>>X>>Y>>Z;
  swap(X,Y);
  swap(X,Z);
  cout<<X<<" "<<Y<<" "<<Z<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define M 1000000007

using namespace std;


int main(){
    int n,k;cin>>n>>k;
    vector <int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int sum=0;
    sort(v.begin(),v.end());
    for(int i=0;i<k;i++){
        sum+=v[i];
    }
    cout<<sum<<endl;
    
}

Measured memory_bytes: 3628
import java.util.*;
import java.lang.*;
import java.util.stream.*;
import java.util.function.*;

// 文字列を一文字ずつ配列にしてStream
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] firstArr = sc.nextLine().split(" ");
        System.out.println(solve(getInputAsArray(sc, "1")));
    }

    private static List<String[]> getInputAsArray(Scanner sc, String count) {
        List<String[]> result = new ArrayList<>();
        IntStream.range(0, Integer.parseInt(count)).forEach(i -> result.add(sc.nextLine().split(" ")));
        return result;
    }

    private static Long[] convertStrToInt(String[] strArray) {
        return Arrays.stream(strArray).map(e -> new Long(Long.parseLong(e))).toArray(Long[]::new);
    }

    private static long outputResult(long a, long b) {
        return LongStream.range(0, b).reduce((long) 0, (sum, i) -> sum += (Math.pow(10, i) * a));
    }

    private static String solve(List<String[]> input) {
        Predicate<String> predicate = (str) -> str.equals("A") || str.equals("B") || str.equals("C");
        BiPredicate<String, String> strCheker = (accum, str) -> {
            // System.out.println(accum + " " + str);
            Map<String, String> map = new HashMap<>();
            map.put("A", "");
            map.put("B", "A");
            map.put("C", "AB");
            return accum.equals(map.get(str));
        };
        ArrayList<String> result = new ArrayList<>();
        Arrays.stream(input.get(0)[0].split("")).reduce("", (accum, value) -> {
            // System.out.println("---" + accum + "----" + value);
            if (value.equals("A")) {
                return "A";
            }
            if (strCheker.test(accum, value)) {
                accum += value;
            } else {
                return "";
            }
            if (accum.equals("ABC")) {
                // System.out.println("avc");
                result.add(value);
                return "";
            }
            return accum;
        });
        return String.valueOf(result.size());
    }
}

class Resp {
    private long min = Long.MAX_VALUE;
    private int cont = 0;

    public Resp(long min, int cont) {
        this.min = min;
        this.cont = cont;
    }

    public long getMin() {
        return this.min;
    }

    public void setMin(long min) {
        this.min = min;
    }

    public int getCont() {
        return this.cont;
    }

    public void setCont(int cont) {
        this.cont = cont;
    }

    public void addCont() {
        this.cont++;
    }

}


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

# define sc second
# define fr first

using namespace std;

long long n, rmax, bmax, bmin = 1e9, rmin = 1e9;;
long long ans = 1e18;
pair<long long, long long> ar[200001];

int main()
{
    cin >> n;
    for(long long i = 1; i <= n; i++)
    {
        cin >> ar[i].fr >> ar[i].sc;
        if(ar[i].fr > ar[i].sc) swap(ar[i].fr, ar[i].sc);
    }

    sort(ar + 1, ar + n + 1);

    for(long long i = 1; i <= n; i++)
        rmax = max(rmax, ar[i].fr), rmin = min(rmin, ar[i].fr), bmax = max(bmax, ar[i].sc), bmin = min(bmin, ar[i].sc);

    ans = (ar[n].fr - ar[1].fr) * (bmax - bmin);

    rmax = bmax, bmin = ar[2].fr;

    long long l = 1e9, r = ar[n].fr;

    for(long long i = 1; i < n; i++)
    {
        l = min(ar[i].sc, l);
        r = max(ar[i].sc, r);

        ans = min(ans, 1ll * (rmax - rmin) * (r - min(l, ar[i + 1].fr)));
    }

    cout << ans;
    return 0;
}




Measured memory_bytes: 3328
/*
1. I'm the Future Red Coder :)
2. Hopefully, I'll be Yellow Soon.
*/
#include<bits/stdc++.h>
#define mod 1000000007
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
ll power(ll a,ll b,ll m=mod) {
    if (b==0) return 1;
    ll c = power(a,b>>1,m);
    c = (c*c)%m;
    if (b&1) return (c*a)%m;
    return c;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}
/*struct node {
    int l,r,nq;
};
bool compare(const node& a,const node& b) {
    if (a.r != b.r) return a.r<b.r;
    return a.l<b.l;
}*/
/* ******* DSU START ****** */
/*
const int dsusize = (int)1e5+5;
struct node {
    int data;
    int rk,pn;
}dsu[dsusize];
//ll fans;
void initialize(int n) {
    REP(i,1,n) {
        dsu[i].data = 1;
        dsu[i].rk = 0;
        dsu[i].pn = i;
    }
}
int fnd(int i) {
    if (dsu[i].pn != i) dsu[i].pn = fnd(dsu[i].pn);
    return dsu[i].pn;
}
void unn(int i,int j) {
    i = fnd(i);
    j = fnd(j);
    if (i!=j) {
        //fans -= dsu[i].data*dsu[j].data;
        if (dsu[i].rk>dsu[j].rk) {
            dsu[j].pn = i;
            dsu[i].data += dsu[j].data;
        }
        else {
            dsu[i].pn = j;
            dsu[j].data += dsu[i].data;
            if (dsu[i].rk==dsu[j].rk) {
                dsu[j].rk++;
            }
        }
    }
}
*/
/* ******* DSU END****** */

const int N = (int)2e5+5;
const int Q = 250;

void solve() {
    int n,a,cnt=0;
    cin>>n;
    REP(i,1,n) {
        cin>>a;
        if (a!=i) cnt++;
    }
    if (cnt>2) cout<<"NO";
    else cout<<"YES";
}
int main() {
    //freopen("class_treasurer.txt","r",stdin);
    //freopen("output.txt","w",stdout);

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

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        cout<<"\n";
    }
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int x1,x2,x3,x4,x5;
  scanf("%d %d %d %d %d",&x1,&x2,&x3,&x4,&x5);
  if(x1==0){
  printf("%d",1);
  }
  else if(x2==0){
  printf("%d",2);
  }
  else if(x3==0){
  printf("%d",3);
  }
  else if(x4==0){
  printf("%d",4);
  }
  else if(x5==0){
  printf("%d",5);
  }
  else{
  	printf("not av");
  }
        }

Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
signed main(){
string s;
  cin>>s;
  if(s=="SAT") cout<<"1\n";
  else if(s=="SUN") cout<<"7\n";
  else if(s=="MON") cout<<"6\n";
  else if(s=="TUE") cout<<"5\n";
  else if(s=="WED") cout<<"4\n";
  else if(s=="THU") cout<<"3\n";
  else if(s=="FRI") cout<<"2\n";
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

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

vector<bool> isp;

void sieve(int x=pow(10,6)+10) {
  isp.resize(x,true); 
  isp[0] = false;
  isp[1] = false;
  for (int i=2; pow(i,2)<=x; i++) {
    if (isp[i]) for(int j=2; i*j<=x; j++) isp[i*j] = false;
  }
}

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

int main() {
  ll N; cin >> N;
  sieve();
 
  vector<ll> ex; 
  for (ll i = 2; i*i<=N; i++) {
    if (isp[i]&&N%i==0) {
      ll now = 0;
      while (N%i==0) {
        N /= i;
        now++;
      }
      ex.push_back(now);
    }
  }
  if (N!=1) ex.push_back(1);
  // debug(all(ex));

  ll result = 0;
  for (auto &x: ex) {
    ll now = 1;
    while (x>=now) {
      result++; x -= now; now++;
    }
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3760
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll s,t,n; cin >> s >> t >> n;
    vector<ll> a(n+1,0);
    for(int i=0;i<n;i++){
        cin >> a[i+1];
        a[i+1]+=a[i];
    }
    ll res=1e18;
    ll dif=s-t;
    for(int i=0;i<=n;i++){
        ll w=dif+a[i];
        if(w<=0){
            res=min(res,(ll)i);
        }
        else{
            if(a[n]>=0)continue;
            res=min(res,(ll)i+(w-a[n]-1)/(-a[n])*n);
        }
    }
    if(res>=1e18){
        printf("-1\n");
    }
    else{
        printf("%lld\n",res );
    }
}


Measured memory_bytes: 3620
import math
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [math.inf]*(h+10000)
dp[0] = 0
for a, b in ab:
    for i in range(h+10000):
        dp[i] = min(dp[i], dp[i-a]+b)
print(min(dp[h:]))

# print(dp[:h+100])


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

#define MAX_V 100000

int N;
vector<pair<int, int>> G[ MAX_V ];
int d[MAX_V];

void dfs( int u, int c )
{
	if( d[u] >= 0 ) {
		return;
	}
	d[u] = c;
	for( int i = 0; i < G[u].size(); i++ ) {
		pair<int, int> e = G[u][i];
		if( e.second % 2 == 0 ) {
			dfs( e.first, c );
		}
		else {
			dfs( e.first, c ^ 1 );
		}
	}
}

int main() {
	cin >> N;
	for( int i = 0; i < N - 1; i++ ) {
		int u, v, w;

		cin >> u >> v >> w;
		u--;
		v--;
		G[u].push_back( make_pair( v, w ) );
		G[v].push_back( make_pair( u, w ) );
	}

	memset( d, -1, sizeof( d ) );
	dfs( 0, 0 );

	for( int i = 0; i < N; i++ ) {
		cout << d[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 8448