akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse4")
#include <cassert>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <math.h>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
mt19937 rnd(random_device{}());
#define all(a) a.begin(), a.end()
#define fr(i, n) for (ll i = 0; i < n; ++i)
#define fr1(i, n) for (ll i = 1; i <= n; ++i)
const int N = 1000001;
int l[N];
void solve() {
    int n; cin >> n;
    fr(i, n) cin >> l[i];
    int cnt = 0;
    fr(i, n) fr(j, i) fr(k, j) {
        vi vec = { l[i], l[j], l[k] };
        sort(all(vec));
        cnt += (vec[0] + vec[1] > vec[2] && vec[0] != vec[1] && vec[1] != vec[2]);
        // if (vec[0] + vec[1] > vec[2]) cout << i << " " << j << " " << k << "\n";
    }
    cout << cnt;
}
void pre_calc() {
}
int main() {
    pre_calc();
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef ABCD
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    int tst = 1;
    if (tst != 1) cin >> tst;
    while (tst--)
        solve();
}

Measured memory_bytes: 3668
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>

template <class Integer>
auto boost_irange(Integer last) { return boost::irange(static_cast<Integer>(0), last); }
template <class Integer>
auto boost_irange(Integer first, Integer last) { return boost::irange(first, last); }

class input
{
    std::istream& cin;

public:
    input() : cin(std::cin)
    {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }

    template <class T>
    inline input& operator>>(T& var)
    {
        cin >> var;
        return *this;
    }
    template <class T>
    inline input& operator,(T& var)
    {
        cin >> var;
        return *this;
    }

    template <class T>
    inline T read()
    {
        T var;
        cin >> var;
        return var;
    }

    template <class InputIterator>
    inline void read(InputIterator head, std::size_t n)
    {
        for (std::size_t i = 0; i < n; ++i) {
            cin >> *head;
            ++head;
        }
    }

    template <class T, class F>
    inline void online(std::size_t n, F&& f)
    {
        T var;
        for (std::size_t i = 0; i < n; ++i) {
            cin >> var;
            f(var);
        }
    }
};
template <class T, std::size_t n>
std::istream& operator>>(std::istream& in, std::array<T, n>& var)
{
    for (std::size_t i = 0; i < n; ++i) {
        in >> var[i];
    }
    return in;
}

class output
{
    std::ostream& cout;

public:
    class proxy
    {
        std::ostream& cout;

    public:
        proxy() : cout(std::cout) {}
        ~proxy() { cout << '\n'; }
        template <class T>
        proxy& operator,(T&& val)
        {
            cout << ' ' << val;
            return *this;
        }
    };

public:
    output() : cout(std::cout)
    {
        cout << std::fixed << std::setprecision(15);
    }

    template <class T>
    proxy operator<<(T&& val)
    {
        cout << val;
        return {};
    }
};

int main()
{
    input in;
    output out;

    int A, B;
    in >> A, B;

    int C = A - B;
    if (C % 2) {
        out << "IMPOSSIBLE";
    } else {
        out << B + C / 2;
    }

    return 0;
}


Measured memory_bytes: 384
package main

import (
	"fmt"
)

func main() {
	var w string
	fmt.Scanf("%s", &w)

	num := make(map[string]int, len(w))

	for i := 0; i < len(w); i++ {
		num[string(w[i])]++
		//fmt.Println(num)
	}

	ans := "Yes"
	for _, x := range num {
		if x%2 != 0 {
			ans = "No"
		}
	}

	fmt.Println(ans)
}


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

typedef long long ll;


int main() {
    int N,M;
    cin >> N >> M;
    vector<int> A(N);
    int sum = 0;
    for (int i=0;i<N;i++){
        cin >> A[i];
        sum += A[i];
    }
    int count = N;
    for (int i=0;i<N;i++){
        if (A[i] < (N%(4*M) == 0 ? N/(4*M) : ceil((double)sum/(4*M)))) {
            count--;
        }
    }
    if (count >= M) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

const int MAXL = 128;
const int Q = 850;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	const string chars = 
		"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
		"abcdefghijklmnopqrstuvwxyz"
		"0123456789";
	assert(chars.size() == 62);

	const bool testing = false;
	string test_ans;
	if (testing) {
		mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
		//int L = uniform_int_distribution<int>(1, MAXL)(mt);
		int L = MAXL-1;
		for (int i = 0; i < L; i++) {
			test_ans += chars[uniform_int_distribution<int>(0, 61)(mt)];
		}
	}
	int query_cnt = 0;
	auto query = [&](string q) -> int {
		query_cnt++;
		cout << '?' << ' ' << q << '\n' << flush;
		int v;
		cin >> v;
		return v;
	};
	auto get_cnt = [&](char c) -> int {
		if (testing) {
			query_cnt++;
			int res = 0;
			for (char v : test_ans) {
				res += v == c;
			}
			return res;
		}
		return MAXL - query(string(MAXL, c));
	};
	vector<int> cnts(62);
	int L = 0;
	for (int i = 0; i < 62; i++) {
		cnts[i] = get_cnt(chars[i]);
		L += cnts[i];
	}
	auto is_subseq = [&](string q) -> int {
		assert(int(q.size()) <= L);
		if (testing) {
			query_cnt++;
			int i = 0;
			for (char c : test_ans) {
				if (c == q[i]) {
					i++;
					if (i == int(q.size())) return true;
				}
			}
			return false;
		} else {
			return query(q) == L - int(q.size());
		}
	};
	auto combine = [&](const string& a, const string& b) -> string {
		string res;
		int ia = 0, ib = 0;
		while (ia < int(a.size()) && ib < int(b.size())) {
			if (is_subseq(a.substr(0, ia+1) + b.substr(ib))) {
				res += a[ia++];
			} else {
				res += b[ib++];
			}
		}
		while (ia < int(a.size())) res += a[ia++];
		while (ib < int(b.size())) res += b[ib++];
		return res;
	};
	function<string(int , int)> solve = [&](int lx, int rx) {
		if (lx + 1 == rx) {
			return string(cnts[lx], chars[lx]);
		} else {
			return combine(solve(lx, (lx + rx) / 2), solve((lx + rx) / 2, rx));
		}
	};
	string ans = solve(0, 62);
	assert(query_cnt <= Q);
	if (testing) {
		assert(ans == test_ans);
	}
	cout << '!' << ' ' << ans << '\n';
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const long long INF = 1LL<<60;
const long long MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max

int main() {

    int n;cin>>n;
    int x[110];
    rep(i,n) {
        cin>>x[i];
    }

    sort(x,x+n);
    
    ll ans=INF;
    for (int i=0;i<=x[n-1];i++) {
        ll p=0;
        for (int j=0;j<n;j++) {
            p+=(x[j]-i)*(x[j]-i);
        }
        ans=min(ans,p);
    }
    
    cout<<ans<<endl;
}

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

int main(){
  int N, max = 0, min = 1000000000, a;
  
  cin >> N;
  for (int i = 0; i < N; i++){
    cin >> a;
    if(a > max){
      max = a;
    }
    if(a < min){
      min = a;
    }
  }
  
  cout << max - min;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<ll,ll>
#define INT_MAX 2147483647
#define MOD 998244353
#define PI 3.14159265358979323846
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;

#define MAX 1000000000000

int main(void) {
	int n; cin >> n;
	vint a(n + 1);
	vint b(n + 1);
	vint c(n + 1);

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}
	for (int i = 1; i <= n - 1; i++) {
		cin >> c[i];
	}


	int p = 100;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += b[a[i]];
		if (p + 1 == a[i]) {
			ans += c[p];
		}
		p = a[i];
	}
	cout << ans << endl;
	return 0;
}


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

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

		String masu = "";
		ArrayList<String> list1 = new ArrayList<String>();
		int cnt = 0;
		// 横
		for (int i = 0; i < H; i++) {
			masu = sc.next();
			for (int j = 0; j < W; j++) {
				if (String.valueOf(masu.charAt(j)).equals("#")) {
					list1.add(masu);
					break;
				}
			}
		}
		H = list1.size();
		String str = "";
		// 縦
		for (int i = 0; i < W; i++) {
			cnt = 0;
			for (int j = 0; j < H; j++) {
				if (String.valueOf(list1.get(j).charAt(i)).equals(".")) {
					cnt++;
				}
			}
			if (cnt == H) {
				for (int k = 0; k < H; k++) {
					str = "";
					for (int l = 0; l < W; l++) {
						if (l != i) {
							str += String.valueOf(list1.get(k).charAt(l));
						}
					}
					list1.set(k, str);
				}
				W--;
				i--;
			}
		}

		for (int i = 0; i < list1.size(); i++) {
			System.out.println(list1.get(i));
		}

		sc.close();
	}

}

Measured memory_bytes: 48540
s = gets.chomp
t = gets.chomp

len = s.length
dic = Hash.new{}
len.times do |i|
	c = s[i]
	if dic[c]
		dic[c].push(i)
	else
		dic[c] = [i]
	end
end

period = 0
now = -1
checker = true
t.length.times do |i|
	char = t[i]
	if dic[char] == nil
		checker = false
		break
	else
		nxt = dic[char].bsearch{|n| n > now}
		if nxt == nil
			nxt = dic[char][0]
			period += 1
		end
		now = nxt
	end
end
if checker
	puts period * len + now + 1
else
	puts '-1'
end

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

signed main() {
  int N,M;
  cin >> N >> M;
  priority_queue<int> A;
  for(int i=0; i<N; i++) {int a; cin >> a; A.push(a); }

  for(int i=0; i<M; i++) {
    int a = A.top(); A.pop();
    A.push(a/2);
  }

  long long ans = 0;
  while(A.size()) { ans+=A.top(); A.pop(); }
  cout << ans << endl;
}


Measured memory_bytes: 892
#!/usr/bin/env python3
import sys
import math

def solve(N: int, K: int):

    ans = int(N/K) ** 3

    if(K%2 == 0):
        cnt = 0
        for i in range(int(K/2), N+1, K):
            cnt += 1
        ans += cnt ** 3
    
    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
CD=[list(map(int,input().split())) for i in range(M)]

def Manhattan(P1,P2):
    ManDis=0
    for i in range(len(P1)):
        ManDis+=abs(P1[i]-P2[i])
    return(ManDis)

for i in range(N):
    ansp=10**10
    ansn=-1
    for j in range(M):
        MD=Manhattan(AB[i],CD[j])
        if ansp>MD:
            ansp=MD
            ansn=j
    print(ansn+1)

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

int n, a, b;

bool can(vector<int>& arr, long long t) {
	long long ret = 0;
	for (int i = 0; i < n; ++i) {
		long long rem = arr[i] - t * b;
		if (rem > 0) ret += (rem - 1) / (a - b) + 1;
	}
	return ret <= t;
}

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

	cin >> n >> a >> b;

	vector<int> arr(n);
	int low = 0, high = 0;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
		high = max(high, arr[i]);
	}

	high = high / b + 1;
	while (high - low > 1) {
		int mid = (low + high) / 2;
		if (can(arr, mid)) high = mid;
		else low = mid;
	}

	cout << high;
}

Measured memory_bytes: 640
const main = stdin => {
  const input = stdin.trim().split('\n')
  const [N, M, X] = input[0].split(' ').map(x => parseInt(x))
  const grid = Array(N + 1)
  const Ms = input[1].split(' ').map(x => parseInt(x))

  let leftCost = 0
  for (let i = X - 1; i > 0; i--) {
    if (Ms.includes(i)) {
      leftCost++
    }
  }

  let rightCost = 0
  for (let i = X; i < N; i++) {
    if (Ms.includes(i)) {
      rightCost++
    }
  }

  console.log(Math.min(leftCost, rightCost))
}


// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


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

const int MAX_N = 100010;
const int INF = 0x3f3f3f3f;

int n, m, s, t, ans;
vector<int> G[MAX_N * 3];
bool vis[MAX_N * 3];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[3 * u].push_back(3 * v + 1);
        G[3 * u + 1].push_back(3 * v + 2);
        G[3 * u + 2].push_back(3 * v);
    }

    cin >> s >> t;
    s--; t--;
    
    ans = INF;
    queue<pair<int, int>> q;
    q.push({s * 3, 0});

    while (!q.empty()){
        pair<int, int> p = q.front(); q.pop();
        
        if (vis[p.first])
            continue;

        if (p.first == t * 3){
            ans = p.second / 3;
            break;
        }

        vis[p.first] = true;
        for (auto i: G[p.first]){
            if (!vis[i])
                q.push({i, p.second + 1});
        }
    }

    cout << ((ans != INF)? ans : -1) << '\n';

    return 0;
}


Measured memory_bytes: 17024
Sd = input()
T  = input()
cand = []
lent = len(T)

for idx in range(len(Sd)-lent+1):
    p = 0
    while p < lent:
        if Sd[idx+p] != T[p] and Sd[idx+p] != "?":
            break

        if p == lent - 1:
            can = ""
            if idx > 0: can = Sd[:idx]
            can += T
            if idx + lent < len(Sd):
                can += Sd[(idx+lent):]
            cand.append(can.replace("?","a"))
        p += 1
if len(cand) == 0:
    print("UNRESTORABLE")
else: 
    cand.sort()
    print(cand[0])


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

int a[100005];

int dst(int m, int w)
{
    if (m % 2)
        return abs(m / 2 + 1 - a[w]);
    return min(abs(m / 2 + 1 - a[w]),
               abs(m / 2 - a[w]));
}

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

    sort(a, a + n);
    int m = a[n - 1];
    cout << m << ' ';
    int s = m / 2 + 1;
    int w = lower_bound(a, a + n, s) - a;
    int bst = (w == n - 1 ? 1e9 : dst(m, w));
    if (w != 0 && dst(m, w - 1) <= bst)
        return cout << a[w - 1], 0;
    cout << a[w];
}


Measured memory_bytes: 640
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<double> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000001
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	int N;
	cin >> N;

	VI T(N);
	VI V(N);

	int Tsum = 0;
	
	double maxv[40010];
	REP(i, 40010) {
		maxv[i] = (double)INF;
	}

	REP(i, N) {
		cin >> T[i];
		Tsum += T[i];
	}
	REP(i, N) {
		cin >> V[i];
	}

	int now = 0;
	REP(i, N) {
		REP(t, T[i]) {
			int a = now + t * 2;
			int b = now + t * 2 + 1;

			maxv[a] = min(maxv[a], V[i]);
			maxv[b] = min(maxv[b], V[i]);
		}
		now += T[i] * 2;
		maxv[now] = min(maxv[now], V[i]);
	}
	maxv[0] = 0.0;
	maxv[Tsum * 2] = 0.0;

	for (int i = 0; i < Tsum * 2+1; i++) {
		maxv[i+1] = min(maxv[i] + 0.5, maxv[i+1]);
	}

	for (int i = Tsum * 2+1; i >= 0; i--) {
		maxv[i] = min(maxv[i + 1] + 0.5, maxv[i]);
	}

	double ans = 0;

	for (int i = 0; i < Tsum * 2 + 1; i++) {
		ans += (maxv[i] + maxv[i + 1]) *0.5/2.0;
	}
	printf("%.4f\n", ans-0.1250);
	return 0;
}



Measured memory_bytes: 640
//Leo
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 200200
using namespace std;
int n,a[N],b[N],mid;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+1+n);
	mid=b[n/2];
	for(int i=1;i<=n;i++) if(a[i]<=mid) printf("%d\n",b[n/2+1]);else printf("%d\n",b[n/2]);
	return 0;
}

Measured memory_bytes: 3712
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
			PrintWriter out=new PrintWriter(System.out);
	FastScanner fs=new FastScanner();
		int a[]=fs.readArray(5);
	int x=0;
	for(int i=0;i<5;i++)
	if(a[i]==0)
	{
	    x=i+1;
	    break;
	}
	out.println(x);
	out.close();
		
	
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
		    return Double.parseDouble(next());
		}
}
}


Measured memory_bytes: 25368
N,S=map(int,input().split())
A=[0]+list(map(int,input().split()))
       
mod = 998244353

note = [[0 for i in range(S+1)] for n in range(N+1)]

for n in range(1,N+1):
  for i in range(1,S+1):
    if A[n]>i:
      note[n][i] = (note[n-1][i]*2) % mod
    elif A[n] == i:
      note[n][i] = (note[n-1][i]*2 + pow(2,n-1,mod)) % mod
      note[n][i] = note[n][i] % mod 
    else:
      note[n][i] = (note[n-1][i] * 2 + note[n-1][i-A[n]]) % mod
      note[n][i] = note[n][i] % mod
  #print(note)
print(note[N][S] % mod)
  
    
       

Measured memory_bytes: 146972
#include<bits/stdc++.h>
#define ll long long
#define M 1000000007
using namespace std;
int dp[100005];
int main()
{ //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
   int n,q;
   cin>>n>>q;
   string s;
   cin>>s;
   for(int i=1;i<n;i++)
   { 
   	  if(s[i]=='C'&&s[i-1]=='A')
   	   dp[i]=dp[i-1]+1;
   	  else
		 dp[i]=dp[i-1]; 
   }
   while(q--)
   {  int  a,b;
   cin>>a>>b;
   cout<<dp[b-1]-dp[a-1]<<"\n";
   	  
   }
  
}

Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

class dice{
public:
  int label[7];
  void turn(char c) {
    int temp;
    if (c=='S') {
      temp=label[1];
      label[1]=label[5];
      label[5]=label[6];
      label[6]=label[2];
      label[2]=temp;
    } else if (c=='E') {
      temp=label[1];
      label[1]=label[4];
      label[4]=label[6];
      label[6]=label[3];
      label[3]=temp;
    } else if (c=='W') {
      temp=label[1];
      label[1]=label[3];
      label[3]=label[6];
      label[6]=label[4];
      label[4]=temp;
    }  else if (c=='N') {
      temp=label[1];
      label[1]=label[2];
      label[2]=label[6];
      label[6]=label[5];
      label[5]=temp;
    } else if (c=='T') {
      temp=label[2];
      label[2]=label[3];
      label[3]=label[5];
      label[5]=label[4];
      label[4]=temp;
    }
  }
  void out(int k){
    cout << label[k] << endl;
  }
};

int main(){
  int i,n,u,m,flag[101];
  dice d1,d2;
  for (i=0;i<101;i++) {
    flag[i]=0;
  }
  for (i=1;i<7;i++){
    cin >> d1.label[i];
    flag[d1.label[i]]=1;
  }
  for (i=1;i<7;i++){
    cin >> d2.label[i];
    if (flag[d2.label[i]]==0) {
      cout << "No" << endl;
      return 0;
    }
  }


  if (d1.label[2]==d2.label[1]) {
    d1.turn('N');
  } else if (d1.label[5]==d2.label[1]) {
    d1.turn('S');
  } else {
    while (d1.label[1]!=d2.label[1]) {
      d1.turn('W');
    }
  }
  while (d1.label[2]!=d2.label[2]) {
    d1.turn('T');
  }
  for (i=3;i<7;i++) {
    if (d1.label[i]!=d2.label[i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}



Measured memory_bytes: 3084
n = int(input())
x = []
u = []
s = 0
for i in range(n):
    x, u = map(str, input().split())
    if u == 'JPY':
      s = s + int(x)
    if u == 'BTC':
      s = s + ( float(x) *  380000.0) 

print(s)

Measured memory_bytes: 2940
#include<iostream>
#include<vector>

using namespace std;
int main(){
    int n,k;
    cin >> n >> k;
    /* 
    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }
    */
    //a/b切り上げ： (a + (b - 1)) / b
    cout << 1+((n-k)+((k-1)-1))/(k-1) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
   int a,b;
   cin >>a>>b;
   if(a < b)
        cout <<"a < b"<<endl;
   else if(a > b)
        cout<<"a > b"<<endl;
    else if(a = b)
        cout<<"a == b"<<endl;
   
   return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n,a[3005];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ll k=i+1,cnt=0;
        for(ll j=1;j<i;j++){
            for(;k<=n;k++){
                if(a[i]+a[j]>a[k]){
                    cnt++;
                }
                else
                    break;
            }
            ans+=cnt;
        }
        
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
from collections import deque

n,m,k= map(int, input().split())

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
visited = [False]*(n+1)
D = {}

for root in range(1,n+1):
    if visited[root]:
        continue
    
    D[root]= set([root])
    d = deque()
    d.append(root)
    while d:
        v = d.popleft()
        visited[v] = True
        gru[v] = root
        for to in fri[v]:
            if visited[to]:
                continue
            D[root].add(to)
            d.append(to)


nans = [0]*n
for i in range(1,n+1):
    g = D[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    nans[i-1] = ans

print(*nans, sep='\n')

Measured memory_bytes: 144640
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}

var mod int

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	s := Scanner()
	x := make([]int, 1)
	x[0] = 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			x[len(x)-1]++
		} else {
			x = append(x, 1)
		}
	}
	ans := 0
	if string(s[0]) == "T" {
		ans += x[0]
		x = x[1:]
	}
	if string(s[len(s)-1]) == "S" {
		ans += x[len(x)-1]
		x = x[:len(x)-1]
	}
	rem := 0
	for i := 0; i < len(x); i += 2 {
		a, b := x[i], x[i+1]
		if a+rem > b {
			rem = a + rem - b
		} else {
			ans += b - a - rem
			rem = 0
		}
	}
	fmt.Println(ans + rem)
}


Measured memory_bytes: 4992
import java.util.*;
import java.io.*;

class Main {

	static int size;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		size = Integer.parseInt(br.readLine());
		String line = br.readLine();

		String[] str = line.split(" ");
		int[] a = new int[size+1];
		for (int i=0; i<size; i++) {
			a[i+1] = Integer.parseInt(str[i]);
		}

		buildMaxHeap(a);

		StringBuilder sb = new StringBuilder();
		for (int i=1; i<size+1; i++) {
			sb.append(" ").append(a[i]);
		}
		System.out.println(sb);
	}

	static void maxHeapify(int[] a,int i){
		int left = i*2;
		int right = i*2+1;
		int largest;
		if (left <= size && a[left] > a[i])
			largest = left;
		else
			largest = i;
		if (right <= size && a[right] > a[largest])
			largest = right;
		if (largest != i) {
			swap(a,i,largest);
			maxHeapify(a,largest);
		}
	}

	static void buildMaxHeap(int[] a){
		for (int i=size/2; i>0; i--) {
			maxHeapify(a,i);
		}
	}

    static void swap(int[] a,int idx1,int idx2){
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }
}


Measured memory_bytes: 75096
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=120;
const int mod=998244353;

int p2[maxn];
int n;
char str[maxn];
__int128 S;

inline void init()
{
	scanf("%s",str+1);n=strlen(str+1);
	p2[0]=1; REP(i,1,n)p2[i]=(p2[i-1]*2)%mod;
	REP(i,1,n)S|=(__int128)(str[i]-'0')<<i-1;
}

ll f[maxn][maxn];

int rem[16][1<<15];

int solve(int len,__int128 a);
int work(int len,__int128 all);

inline int solve(int len,__int128 a)
{
	if(len<=15 && ~rem[len][a])return rem[len][a];
	int ans=0;
	REP(j,2,len)if(len%j==0)
	{
		__int128 t=0;
		int nlen=len/j,num=0;
		REP(k,0,nlen-1)
		{
			t|=1ll<<k;
			REP(x,0,j-1)
			{
				t&=~((~a>>x*nlen+k&1)<<k);
				//cerr<<(ll)a<<endl;
				//cerr<<(ll)(~a>>x*nlen+k&1)<<" "<<(ll)~((~a>>x*nlen+k&1)<<k)<<endl;
			}
		}
		//cerr<<(ll)t<<endl;
		REP(j,0,nlen-1)num+=t>>j&1;
		ans=(ans+work(nlen,t))%mod;
	}
	if(len<=15)rem[len][a]=ans;
	return ans;
}

int dp[maxn];

inline int work(int n,__int128 all)
{
	int f[120][120]={0},dp[120]={0};
	REP(l,1,n)REP(r,l,n)
	{
		__int128 a=0;
		REP(k,l,r)a|=(__int128)(all>>k-1&1)<<k-l;
		f[l][r]=solve(r-l+1,a);
	}
	dp[0]=1;
	REP(i,1,n)
	{
		dp[i]=0;
		REP(j,0,i-1)
		{
			int res=0;
			DREP(k,i,j+1)
			{
				if(all>>k-1&1)res=(ll)res*2%mod;
				res=(res+f[k][i])%mod;
			}
			dp[i]=(dp[i]+(ll)res*dp[j])%mod;
		}
	}
	int ans=dp[0];
	REP(j,1,n)ans=((ll)ans*(1+(all>>j-1&1)) + dp[j] )%mod;
	return ans;
//printf("%d\n",ans);
}

int main()
{
	init();
	memset(rem,-1,sizeof(rem));
	printf("%d\n",work(n,S));
	return 0;
}


Measured memory_bytes: 2688
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    rep(i,N) cin >> L[i];
    sort(all(L));
    ll ans = 0;
    rep(i,N-2)srep(j,i+1,N-1) {
        int ub = L[i] + L[j] - 1;
        // lb <= c <= ub
        auto iter_ub = upper_bound(all(L), ub);
        int dist = iter_ub - L.begin();
        //cout << L[i] << " " << L[j] << " " <<  (dist-(j)) << endl;
        ans += (ll)(dist-(j+1));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
DIR = {'>': (0, 1),
       '<': (0, -1),
       '^': (-1, 0),
       'v': (1, 0)}

while True:
    w, h = map(int, raw_input().split())
    if w == 0 and h == 0:
        break

    m = [[] for i in range(w)]
    for i in range(w):
        m[i] = [c for c in raw_input().strip()]

    x = 0
    y = 0
    while m[x][y] != '.':
        if m[x][y] == 'x':
            break
        else:
            d = m[x][y]
            m[x][y] = 'x'
            x += DIR[d][0]
            y += DIR[d][1]

    if m[x][y] == '.':
        print("{} {}".format(y, x))
    else:
        print("LOOP")

Measured memory_bytes: 4332
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var cin = new Scanner2();
			long n = cin.Long();
			long a = cin.Long();
			long b = cin.Long();

			long m = n / (a + b);
			long r = n % (a + b);

			long ans = m * a;
			ans += r >= a ? a : r;

			Console.WriteLine(ans);
		}
	}

	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private readonly Func<string> reader_;
		private string[] buf_;
		private int index_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

Measured memory_bytes: 11220
from itertools import product
A, B, C, D = list(input())
for op1, op2, op3 in product(("+", "-"), repeat=3):
    e = A + op1 + B + op2 + C + op3 + D
    x = eval(e)
    if x == 7:
        print(e + "=7")
        break


Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;

#define mkp make_pair
#define eb emplace_back
#define sz(s) (int)(s.size())
 
main (){
	clog << "Ready\n";
	
	int k, m;
	cin >> m >> k;
	
	if ((m == 1 && m == k) || (k >= (1 << m)))
        return cout << -1, 0;
    
    if (!k) {
        for (int i = 0; i < (1 << m); ++ i)
            cout << i << " " << i << " ";
        return 0;
    }
    
    cout << "0 " << k << " 0 ";
    
    for (int i = 1; i < (1 << m); ++ i)
        if (i != k)
            cout << i << " ";
    
    cout << k << " ";
    for (int i = (1 << m) - 1; i > 0; -- i)
        if (i != k)
            cout << i << " ";
	
	cerr << '\n';
	return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
    int n,n1[3],i=3,r=0;
    scanf("%d",&n);
    while(n>0 && i>=0)
    {
        i--;
        r=n%10;
        n1[i]=r;
        n=n/10;
    }
    for(i=0;i<3;i++)
    {
        if(n1[i]==1)
        {
            n1[i]=9;
        }
        else if(n1[i]==9)
        {
            n1[i]=1;
        }
    }
    n=(n1[0]*100)+(n1[1]*10)+n1[2];
    printf("%d\n",n);
    return 0;
}


Measured memory_bytes: 128
// copied
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 2010;
int n, m;
int h[N], sta[N];
bool mp[N][N];
char s[N][N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%s", s[i] + 1);
	for (int i = 1; i < n; ++i){
		for (int j = 1; j < m; ++j){
			mp[i][j] =
					(s[i][j] ^ s[i][j + 1] ^ s[i + 1][j] ^ s[i + 1][j + 1])
							== 0 ? 1 : 0;
//			printf("%d", mp[i][j]);
		}
//		printf("\n");
	}
	int ans = max(n, m);
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < m; ++j) {
			h[j] = (h[j] + 1) * mp[i][j];
//			printf("%d ", h[j]);
		}
//		printf("\n");
		int top = 0;
		for (int j = 1; j <= m; ++j) {
			while (top && h[sta[top]] >= h[j]) {
				ans = max(ans, (h[sta[top]] + 1) * (j - sta[top - 1]));
				--top;
			}
			sta[++top] = j;
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 11684
num_of_alpha = dict()

for i in range(97, 123):
    num_of_alpha[chr(i)] = 0

while True:
    try:
        x = input().lower()
        for i in range(len(x)):
            if x[i].isalpha():
                num_of_alpha[x[i]] += 1
    except:
        break

for k, v in num_of_alpha.items():
    print("{} : {}".format(k, v))


Measured memory_bytes: 5560
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    string s;
    cin >> s;
    if ((s[0] == s[1] && s[0] == s[2]) || (s[1] == s[2] && s[1] == s[3])) {
        cout << "Yes" << endl;
    } else cout << "No" << endl;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

int n;
vector<vector<pair<int, ll> > > G;
int q, k;
vector<ll> dis;

void dfs(int i, int j) {
    for(auto nexti:G[i]) {
        if(nexti.first == j) continue;
        dis[nexti.first] = dis[i] + nexti.second;
        dfs(nexti.first, i);
    }
}

int main() {
    
    cin >> n;
    G.resize(n);
    rep(i, n-1) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        G[a-1].push_back(make_pair(b-1, c));
        G[b-1].push_back(make_pair(a-1, c));
    }
    
    cin >> q >> k;
    vi x(q), y(q);
    rep(i, q) {
        int x_, y_;
        cin >> x_ >> y_;
        x[i] = x_-1;
        y[i] = y_-1;
    }

    dis.resize(n);
    dis[k-1] = 0;
    dfs(k-1, -1);

    rep(i, q) {
        cout << dis[x[i]]+dis[y[i]] << '\n';
    }
}

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

class Dice{
private:
  int tmp;
public:
  int q[6];
  void roll(char d){
    if(d=='N'){
      tmp = q[4];
      q[4] = q[0];
      q[0] = q[1];
      q[1] = q[5];
      q[5] = tmp;
    } else if(d=='E'){
      tmp = q[2];
      q[2] = q[0];
      q[0] = q[3];
      q[3] = q[5];
      q[5] = tmp;
    } else if(d=='W'){
      tmp = q[3];
      q[3] = q[0];
      q[0] = q[2];
      q[2] = q[5];
      q[5] = tmp;
    } else if(d=='S'){
      tmp = q[1];
      q[1] = q[0];
      q[0] = q[4];
      q[4] = q[5];
      q[5] = tmp;
    }
  }
};


int main(){
  Dice d, e;
  for(int i=0; i<6; i++){
    cin >> d.q[i];
  }
  for(int i=0; i<6; i++){
    cin >> e.q[i];
  }

  for(int i=0; i<=6;i++){//上の面を揃える
    //cout << "a";
    if(i==5){
      d.roll('E');
    } else if(i==6) {
      d.roll('E');
      d.roll('E');
    } else d.roll('N');
    //cout << d.q[0] << " " << d.q[1] << endl;
    if(d.q[0]==e.q[0])break;
  }
  for(int i=0; i<=4;i++){//上の面を固定したまま、横の面をぐるっと一周
    //cout << "b";
    d.roll('E');
    d.roll('N');
    d.roll('W');
    //cout << d.q[0] << " " << d.q[1] << endl;
    if(d.q[0]==e.q[0]&&d.q[1]==e.q[1])break;
  }
  int ans=1;
  for(int i=0; i<6; i++){
    ans*=(d.q[i]==e.q[i]);
  }
  if(ans==0)cout << "No" << endl;
  else cout << "Yes" << endl;
}



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

using namespace std;

using ll = long long;

const ll INF = 1000000000000000LL;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<ll> a(n);
	vector< vector<ll> > dp(n, vector<ll>(n + 1, INF));
	vector<ll> sum(n + 1, 0);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		dp[i][i] = 0;
		dp[i][i + 1] = 0;
		sum[i + 1] = sum[i] + a[i];
	}

	for (int j = 2; j <= n; j++) {
		for (int i = 0; i + j <= n; i++) {
			for (int k = i + 1; k < i + j; k++) {
				dp[i][i + j] = min(dp[i][i + j], dp[i][k] + dp[k][i + j] + sum[i + j] - sum[i]);
			}
		}
	}
	cout << dp[0][n] << endl;
	return 0;
}

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

#define int long long
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; }

signed main(){
	int n;
	cin >> n;

	cout << (1000-n%1000)%1000 << endl;

	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define u unsigned
#define N1 100005
#define N2 200005
#define endl "\n"
#define mod 1000000007
#define vll vector<ll>
#define pb push_back
#define vi vecctor<int>
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)

int main()
{
    ll t,n,n1,n2;
    t=1;
    while(t--)
    {
		cin>>n;
		int a[n+1][3];
		for1(i,n)
		{
			cin>>a[i][0]>>a[i][1]>>a[i][2];
		}

		int dp[n+1][3];
		for1(i,n)
		{
			if(i==1)
			{
				dp[i][0]=a[1][0];
				dp[i][1]=a[1][1];
				dp[i][2]=a[1][2];
				continue;
			}
			
			dp[i][0]=a[i][0]+max(dp[i-1][1],dp[i-1][2]);
			dp[i][1]=a[i][1]+max(dp[i-1][0],dp[i-1][2]);
			dp[i][2]=a[i][2]+max(dp[i-1][0],dp[i-1][1]);
		}

		cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
        
    }
    return 0;
}


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

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for(int i=n; i>=1; i--){
    if((double)sqrt(i) == (int)sqrt(i)){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
ans=0
Br=[0]*N
for i in range(N):
    t=bisect.bisect_left(A,B[i])
    if(i==0):
        Br[i]=t
    else:
        Br[i]=Br[i-1]+t
for i in range(N):
    t=bisect.bisect_left(B,C[i])
    if(t==0):
        continue
    ans+=Br[t-1]
print(ans)

Measured memory_bytes: 23092
#include <bits/stdc++.h>
using namespace std;
#define fin(ans) cout << ans << endl

int main(void) {
  int N, i;
  cin >> N;
  for (i = N * 0.92; i <= N; i++) {
    if (int(i * 1.08) == N) {
      fin(i);
      break;
    }
  }
  
  if(i == N + 1)
    cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>

using namespace std;

#define mod 1000000007

int main()
{
	int n, m;
	cin >> n >> m;
	int graph[8][8] = {};
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		graph[a][b] = graph[b][a] = 1;
	}
	int result[1 << 8][8][8] = {};
	// result[i][j][k]: iを二進数表現で通る頂点、jスタートでkが終わりになるような通り方
	for(int i = 0; i < n; i++){
		result[1 << i][i][i] = 1;
	}
	for(int i = 0; i < (1 << n); i++){
		for(int j = 0; j < n; j++){
			if((i & (1 << j)) == 0) continue;
			for(int k = 0; k < n; k++){
				if((i & (1 << k)) == 0) continue;
				// jスタートでkが終わりとする
				for(int l = 0; l < n; l++){
					if((i & (1 << l)) != 0 || graph[k][l] == 0) continue;
					// l: 次に通る頂点
					result[i | (1 << l)][j][l] += result[i][j][k];
				}
				// cout << i << " " << j << " " << k << " " << result[i][j][k] << endl;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans += result[(1 << n) - 1][0][i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

const ll MOD=998244353ll;

int main()
{
  string s;
  cin>>s;
  int n=s.size();
  if(n==2){
    if(s[0]==s[1]) cout<<1<<endl;
    else cout<<2<<endl;
    return 0;
  }else if(n==3){
    if(s[0]==s[1] && s[1]==s[2]){
      cout<<1<<endl;
    }else if(s[0]!=s[1] && s[1]!=s[2] && s[2]!=s[0]){
      cout<<3<<endl;
    }else if(s[0]==s[2]){
      cout<<7<<endl;
    }else{
      cout<<6<<endl;
    }
    return 0;
  }
  int m=0;
  bool diff=1;
  bool same=1;
  ll all=1;
  for(int i=0; i<n; i++){
    if(i+1<n) all=all*3%MOD;
    m+=(s[i]-'a');
    m%=3;
    if(i+1<n && s[i]==s[i+1]) diff=0;
    if(i+1<n && s[i]!=s[i+1]) same=0;
  }
  if(same){
    cout<<1<<endl;
    return 0;
  }
  ll dp[3][3][200001]={};
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      if(i==j) dp[i][i][1]=1;
      else dp[i][j][1]=0;
    }
  }
  for(int k=2; k<=n; k++){
    for(int i=0; i<3; i++){
      for(int j=0; j<3; j++){
        dp[(i+j+1)%3][(j+1)%3][k]+=dp[i][j][k-1];
        dp[(i+j+1)%3][(j+1)%3][k]%=MOD;
        dp[(i+j+2)%3][(j+2)%3][k]+=dp[i][j][k-1];
        dp[(i+j+2)%3][(j+2)%3][k]%=MOD;
      }
    }
  }
  ll ans=0;
  for(int i=0; i<3; i++){
    ans+=dp[m][i][n];
  }
  ans%=MOD;
  if(!diff){
    ans=(all-ans+MOD)%MOD;
  }else{
    ans=(all-ans+MOD+1)%MOD;
  }
  cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 14596
#include <iostream>

using namespace std;

char board[102][102] = {{0}};

int main() {
  int H, W;
  cin >> H >> W;

  for (int i = 1; i <= H; ++i) {
    for (int j = 1; j <= W; ++j) {
      cin >> board[i][j];
    }
  }

  for (int i = 1; i <= H + H; ++i) {
    for (int j = 1; j <= W; ++j) {
      printf("%c", board[(i + 1) / 2][j]);
    }
    printf("\n");
  }
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:512000000")
#include<utility>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

//4Head

#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(NULL));

ll const mod = 1e9 + 7;

namespace {
	ll mul(ll a, ll b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) val += mod;
		if (val >= mod) val -= mod;
		return val;
	}

	ll poww(ll a, ll b) {
		ll val = 1;
		a %= mod;
		while (b > 0) {
			if (b % 2) val = mul(a, val);
			a = mul(a, a);
			b >>= 1;
		}
		return val % mod;
	}

	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

ll const maxn = 3e5 + 5;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll t = (-11 + 4) / 5;
	ll n, k; cin >> n >> k;
	vector<ll>a(n);
	for (ll i = 0; i < n; i++) cin >> a[i];
	sort(all(a));
	ll l = -3e18, r = 3e18;
	//k++;
	while (r - l > 1) {
		ll m = (l + r) / 2;
		//m = 6;
		ll kek = 0;
		for (ll i = 0; i < n; i++) {
			ll y = a[i];
			ll cnt;
			if (y > 0) {
				ll b = m / y; if (y * b > m) b--;
				cnt = (b >= a[0] ? upper_bound(all(a), b) - begin(a) : 0); 
				cnt = min(i, cnt);
			} else if (y < 0) {
				cnt = begin(a) + i - lower_bound(all(a), m / y); cnt = max(0LL, cnt); cnt = min(cnt, i);
			} else {
				if (m >= 0) cnt = i;
				else cnt = 0;
			}
			kek += cnt;
		}
		if (kek >= k) {
			r = m;
		} else {
			l = m;
		}
	}
	cout << r << endl;
	return 0;
}

/*
3
0 1
3 0
1 0
*/

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main{
	public static void main(String[]args){
	Scanner sc = new Scanner(System.in);
	int x = sc.nextInt();
	int y = sc.nextInt();
	int z = sc.nextInt();
	  if(x < y){
	if(y < z){
	System.out.printf("%d %d %d\n",x,y,z);	
	}
	else if(x < z){
	System.out.printf("%d %d %d\n",x,z,y);	
	}
	else{
	System.out.printf("%d %d %d\n",z,x,y);	
	}
	}
	  if(x > y){
	if(x < z){
	System.out.printf("%d %d %d\n",y,x,z);	
	}
	else if(y < z){
	System.out.printf("%d %d %d\n",y,z,x);	
	}
	else{
	System.out.printf("%d %d %d\n",z,y,x);	
	}
}
}
}


Measured memory_bytes: 26460
#include<cstdio>
#include<cstring>
const int MAXN = 3 * int(1E5);
char s[MAXN + 5];
int sum[MAXN + 5];
int main() {
	int N;
	scanf("%d %s", &N, s+1);
	for(int i=1;i<=N;i++) {
		if( s[i] == 'W' ) {
			sum[i+1]++;
			sum[N+1]--;
		}
		else {
			sum[1]++;
			sum[i]--;
		}
	}
	int ans = MAXN + 5;
	for(int i=1;i<=N;i++) {
		sum[i] += sum[i-1];
		if( sum[i] < ans )
			ans = sum[i];
	}
	printf("%d\n", ans);
	return 0;
}

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

int main() {
    int N, M;
    cin >> N >> M;
    int ans = N*(N - 1)/2 + M*(M - 1)/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256