akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;
class Program
{
    public static Scanner cin;
    static void Main()
    {
        
        cin = new Scanner();
        long[] nm = cin.arrayLong(2);
        long n = nm[0];
        long m = nm[1];
        long[][] ab = new long[n][];
        for(int a = 0; a < n; a++)
        {
            ab[a] = cin.arrayLong(2);
        }
        ab = ab.OrderBy(i => i[0]).ToArray();
        long total = 0;
        long count = 0;
        for(int a = 0; a < ab.Length; a++)
        {
            for(int b=0;b< ab[a][1]; b++)
            {
                total += ab[a][0];
                count++;
                if (count == m) break;
            }
            if (count == m) break;
        }
        WriteLine(total);
        ReadLine();

    }
}





class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string input()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return input();
        i = 0;
        return s[i++];
    }

    public int inputInt()
    {
        return int.Parse(input());
    }
    public int[] arrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = inputInt() + add;
        }
        return Array;
    }

    public long inputLong()
    {
        return long.Parse(input());
    }

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

    public double inputDouble()
    {
        return double.Parse(input());
    }


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

Measured memory_bytes: 29248
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include <cmath>
#include <limits>

using namespace std;
#define int long  long int
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main()
{
	int A, B;
	cin >> A >> B;
	int len = A - 2 * B;
	if (len < 0)len = 0;
	cout << len;
}

Measured memory_bytes: 256
N = int(input())
S = input()

RGB = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = 2 * j - i
    if ( k >= N ):
      break
    if (S[i] != S[j]) & (S[j] != S[k]) & (S[i] != S[k]):
      RGB -= 1


print(RGB)

Measured memory_bytes: 9196
K, N = list(map(int,input().split()))
A = list(map(int,input().split()))
d = [A[i+1]-A[i] for i in range(N-1)]
de = K - A[N-1] + A[0]
d.append(de)
D = sorted(d)
dis = 0
for i in range(N-1):
  dis += D[i]
print(dis)

Measured memory_bytes: 26444
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int Mod = 998244353;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a,b); }
void Dec(int &a, int b){ a = dec(a,b); }
cs int N = 3e3 + 50;
int dp[N][N], A, B, C, D;
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d%d%d%d",&A,&B,&C,&D);
	dp[A][B] = 1;
	for(int i=A; i<=C; i++)
	for(int j=B; j<=D; j++){
		Add(dp[i][j],mul(j,dp[i-1][j]));
		Add(dp[i][j],mul(i,dp[i][j-1]));
		Dec(dp[i][j],mul(mul(i-1,j-1),dp[i-1][j-1]));
	} cout<<dp[C][D]; return 0;
}

Measured memory_bytes: 39236
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define int ll
#define pb push_back
#define sz(i) (int)(i.size())
#define fi first
#define se second
#define ld long double
#define pii pair<int, int>
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = 1e9 + 7;
using namespace std;
#ifndef ONLINE_JUDGE
#define tr(...) {__l(__LINE__);__f(#__VA_ARGS__, __VA_ARGS__);}
inline void __l(int line) { cerr << "#" << line << ": "; }template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define tr(...)
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}template<typename T>inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v){bool first = true;os << "[";for(auto i: v){if(!first)os << ", ";os << i;first = false;}return os << "]";}
const int N = 5*1e5 + 10;
// make sure N size is correctttt!!!!!!!!!


int a, b, c, ans;
int32_t main(){_

   cin>>a>>b>>c;

   if((c-(a+b)) <= 0){
      ans += c+b;
      cout<<ans;
   }
   else{
      c -= a;
      ans += a;
      c -= b;
      ans += b*2;
      ans++;
      cout<<ans;
   }

   //make sure N size is correct!!!!!!!!!
   return 0;
}

Measured memory_bytes: 256
N = int(input())
a = [int(i) for i in input().split()]

renga_num = 1
kudaku = 0
for i in range(N):
    if a[i] == renga_num:
        renga_num += 1
    else:
        kudaku += 1

if kudaku == N:
    print(-1)
else:
    print(kudaku)

Measured memory_bytes: 77644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[1001][1001];

int main(){
  ll n,k;
  cin>>n>>k;
  n-=k;
  
  for(int i=0;i<=k;i++){
    dp[i][0]=1;
    for(int j=1;j<=n;j++){
      if(j-i>=0)
        dp[i][j]+=dp[i][j-i];

      if(i-1>=0)
        dp[i][j]+=dp[i-1][j];
      
      dp[i][j]%=mod;
    }
  }
  if(n>=0)cout<<dp[k][n]<<endl;
  else cout<<0<<endl;
  return 0;
}



Measured memory_bytes: 7384
//////////////////////////
/*      _        ____   */
/*  U  /"\  u U /"___|  */
/*   \/ _ \/  \| | u    */
/*   / ___ \   | |/__   */
/*  /_/   \_\   \____|  */
/*   \\    >>  _// \\   */
/*  (__)  (__)(__)(__)  */
/*   Compro by emame©   */
//////////////////////////
#include<iostream>
#include<string>
using namespace std;
int main() {
  
  int a, b, c, d;
  cin >> a >> b;

  cout << a * b << " " << 2 * (a + b) << endl;
  
  return (0);
}


Measured memory_bytes: 3076
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;

int main(void) {
	int a, b;
	cin >> a >> b;
	if (a > 8) {
		cout << ":(" << endl;
	}
	else {
		if (b > 8) {
			cout << ":(" << endl;
		}
		else {
			cout << "Yay!" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
S = str(input())

count = S.count('E')

if S[0] == 'E':
	count-=1

countmin = count

for i in range (1, N):
	if S[i] == 'E':
		count-=1
	if S[i-1] == 'W':
		count+=1
	if count < countmin:
		countmin = count

print(countmin) 

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

long long int gcd(long long int a,long long int b){
	if (a == 0)
		return b;
	return gcd(b % a, a);
}
long long int lcm(long long int a,long long int b)
{
	return (a*b)/gcd(a, b);
}

int main()
{
	long long int a,b,g;
	cin>>a>>b;
	g=gcd(a,b);
	cout<<lcm(a, b);
	return 0;
}


Measured memory_bytes: 256
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate
from bisect import bisect_right

n,x = li()
a = list(li())

a.sort()
a_cum = list(accumulate(a))


if x == a_cum[-1]:
    print(n)

elif x > a_cum[-1]:
    print(n-1)
    
else:
    ans = bisect_right(a_cum, x)
    print(ans)

Measured memory_bytes: 3444
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        int next_combination(int sub) {
            int x = sub & -sub, y = sub + x;
            return (((sub & ~y) / x) >> 1) | y;
        }

        void solve(InputReader in, PrintWriter out) {
            int N = in.nextInt();
            char[] march = new char[] {'M', 'A', 'R', 'C', 'H'};

            Map<Character, Integer> cntByIni = new HashMap<>();
            for (char c : march) cntByIni.put(c, 0);

            for (int i = 0; i < N; i++) {
                char ini = in.next().charAt(0);
                if (cntByIni.containsKey(ini)) {
                    cntByIni.put(ini, cntByIni.get(ini) + 1);
                }
            }

            long ans = 0;
            int mask = (1 << 3) - 1;
            for (; mask < (1 << 5); mask = next_combination(mask)) {
                long pattern = 1;
                for (int i = 0; i < 5; i++) {
                    if ((mask >> i & 1) == 1) {
                        pattern *= cntByIni.get(march[i]);
                    }
                }
                ans += pattern;
            }

            out.println(ans);
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Measured memory_bytes: 36944
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String[] params = sc.nextLine().split(" ");
        long h = Long.parseLong( params[0] );
        int n = Integer.parseInt( params[1] );

        params = sc.nextLine().split(" ");
        int[] as = new int[n];
        long total = 0;
        for( int i = 0 ; i < n ; i++ ){
            as[i] = Integer.parseInt( params[i] );
            total += as[i];
        }

        System.out.println( h > total ? "No" : "Yes" );

    }

}


Measured memory_bytes: 49956
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        
        int div = a / b;
        int rem = a % b;
        double fp = (double)a / (double)b;
        
        String after = String.format("%.16f", fp);
        System.out.println(div + " " + rem + " " + after); 
    }
}

Measured memory_bytes: 26420
N = int(input())
eatingOrder = list(map(int, input().split()))
points = list(map(int, input().split()))
bonusPoints = list(map(int, input().split()))

sutisfactionPoint = 0
beforeFood = -1
for food in eatingOrder:
    sutisfactionPoint += points[food-1]

    if beforeFood+1 == food:
        sutisfactionPoint += bonusPoints[beforeFood-1]
    
    beforeFood = food
print(sutisfactionPoint)

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	VI a={0, 1,6,8};
	string ans ="hon";
	n%=10;
	if(n==3) ans = "bon";
	else{
		rep(j, 4) if(n==a[j]) ans="pon";
	}
	cout <<ans <<"\n";
	return 0;
	
}


Measured memory_bytes: 3644
//Apparat : drobucs, aleonov, vit_72
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <iomanip>
#include <algorithm>
#include <string>
#include <queue>
#include <numeric>
#include <stack>

//#pragma warning(disable : 4996)
//#pragma GCC optimize("O3")

using namespace std;

#define nptr nullptr
#define all(x) (x).begin(), (x).end()
#define drobucs ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()

typedef  long long ll;

const int maxn = (int)1e6 + 13;
const ll INFL = 9223372036854775807;
const ll INF = 2147483647;
const ll MOD = (int)1e9 + 7, MOD2 = 998244353;//1e9 + 21, 1e9 + 33, 1e9 + 87, 1e9 + 93
const ll base = 101, base2 = 37;

int a[maxn];
int x[maxn];
bool vis[maxn];

int main() {
	drobucs;
	
	ll n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)cin >> a[i];
	int now = 1;
	vector<int> cicle;
	if (k <= 4 * n) {
		int ans = 1;
		for (int i = 0; i < k; ++i) ans = a[ans];
		cout << ans << "\n";
		return 0;
	}
	for (int i = 1; i <= 4 * n; ++i) { 
		x[now]++;
		if (x[now] == 2)cicle.push_back(now);
		now = a[now];
	}
	int y = 0;
	for (int i = 1; i <= n; ++i)if (x[i] == 1)++y;
	k -= y;
	cout << cicle[k % sz(cicle)] << "\n";
	return 0;
}

Measured memory_bytes: 5328
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

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

const ll mod = 1000 * 1000 * 100 + 7;


int R, C;
int memo[10][10][200000];
char field[10][10];

inline vector<int> decode(int mask){
  vector<int> v(C + 1);
  REP(i, C + 1){
    v[i] = mask % 3;
    mask /= 3;
  }
  return v;
}

inline int encode(const vector<int> &v){
  int mask = 0;
  int N = 1;
  REP(i, C + 1){
    mask += v[i] * N;
    N *= 3;
  }
  return mask;
}

int calc(int r, int c, int mask){
  if(r == R) return mask == 0;
  if(c == C) return mask % 3 == 0 ? calc(r + 1, 0, mask) : 0;
  
  if(memo[r][c][mask] != -1) return memo[r][c][mask];
  int &res = memo[r][c][mask] = 0;
  vector<int> v = decode(mask);
  int left = v[0];
  int down = v[c+1];
  
  if(field[r][c] == 0){
    if(left == 0 || down == 0){
      res = calc(r, c + 1, mask);
    }
  }else{
    int rest = field[r][c] - left - down;
    REP(nleft, 3){
      int ndown = rest - nleft;
      if(0 <= ndown && ndown <= 2){
        v[0] = nleft;
        v[c+1] = ndown;
        res += calc(r, c + 1, encode(v));
        res %= mod;
      }
    }
  }
  return res ;
}
 

int main(){
  cin >> R >> C;
  REP(i, R)REP(j, C){
    cin >> field[i][j];
    field[i][j] = isdigit(field[i][j]) ? field[i][j] - '0' : 0;
  }
  memset(memo, -1, sizeof(memo));
  cout << calc(0, 0, 0) << endl;
  
  return 0;
}

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

int main()
{
    int h, w;
    char c[] = {'#', '.'};
    while (true)
    {
        cin >> h >> w;
        if (h == 0 && w == 0)
            break;
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                cout << c[(i + j) % 2];
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int main(){
	ll n, m, k, ma1 = -1, ma2 = -1;
	cin >> n >> m >> k;
	ll x[k], y[k];
	map<ll, ll> m1, m2;
	set<ll> s1, s2;
	for (int i = 0; i < k; i++){
		cin >> x[i] >> y[i];
		m1[x[i]]++, m2[y[i]]++;
	}
	for (auto e : m1){
		if (e.ss > ma1){
			s1.clear();
			ma1 = e.ss, s1.emplace(e.ff);
		}else if (e.ss == ma1){
			s1.emplace(e.ff);
		}
	}
	for (auto e : m2){
		if (e.ss > ma2){
			s2.clear();
			ma2 = e.ss, s2.emplace(e.ff);
		}else if (e.ss == ma2){
			s2.emplace(e.ff);
		}
	}
	ll ans = (ll)s1.size() * (ll)s2.size();
	for (ll i = 0; i < k; i++){
		if (s1.find(x[i]) != s1.end() && s2.find(y[i]) != s2.end()) ans--;
	}
	if (ans == 0) printf("%lld\n", ma1 + ma2 - 1);
	else printf("%lld\n", ma1 + ma2);
}

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

int main() {

  string s;
  cin >> s;

  int Q;
  cin >> Q;

  // Tの回数
  int countT = 0;

  deque<char> S;
  for (int i = 0; i < s.size(); i++) {
    S.push_back(s[i]);
  }

  for (int i = 0; i < Q; i++) {
    int T;
    cin >> T;
    if (T == 1) {
      countT++;
    } else {
      int F;
      char C;
      cin >> F >> C;
      if (F == 1) {
        if (countT % 2 == 0) {
          // 前に加える
          S.push_front(C);
        } else {
          // 後ろ加える
          S.push_back(C);
        }
      } else {
        if (countT % 2 == 0) {
          // 後ろに加える
          S.push_back(C);
        } else {
          // 前に加える
          S.push_front(C);
        }
      }
    }
  }

  if (countT % 2 == 0) {
    // 前から出力
    while (!S.empty()){
      cout << S.front();
      S.pop_front();
    }
  } else {
    // 後ろから出力
    while (!S.empty()){
      cout << S.back();
      S.pop_back();
    }
  }
  cout << endl;

  return 0;

}

Measured memory_bytes: 896
import java.util.Scanner;
import java.util.*;

public class Main{
	public static void main(String[] args)
	{
		Scanner sc =new Scanner(System.in);
		String s = sc.next();	//入力された文字列
		StringBuilder sb = new StringBuilder();	//sbを用意

		//キーによって挿入される文字を変化
		for(int i=0;i<s.length();i++){
			if(s.charAt(i)=='0') sb.append("0");
			else if(s.charAt(i)=='1') sb.append("1");
			else if(s.charAt(i)=='B'){
				//sbに要素が入っている時だけ文字をdelete
				if(sb.length()!=0) sb.deleteCharAt(sb.length()-1);
			}
		}
		
		//結果を出力
		System.out.println(sb.toString());
	}
} 

Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int main() {
	int a, b;
	cin >> a >> b;
	for (int i = 0; i <= 2000; i++) {
		int A = i * 8 / 100;
		int B = i / 10;
		if (a == A && b == B) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;
int main(int argc, char const *argv[]) {
  vll n{1};
  re(i, 20) n.push_back(n[n.size()-1]*2);
  ll t;std::cin >> t;
  ll i = upper_bound(all(n), t) - n.begin();
  std::cout << n[i-1] << '\n';
}


Measured memory_bytes: 256
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100000+9;
struct E{
	int next,to;
}edge[MAXN<<1];
int head[MAXN],edge_num;
int n;
int degree[MAXN];
int dp[MAXN];
int A,B;
int limit;

void addedge(int x,int y){
	degree[x]++;
	edge[++edge_num].next=head[x];
	edge[edge_num].to=y;
	head[x]=edge_num;
}

bool DP(int x,int fa){
	vector<int> vec;
	int cnt=0;
	if(degree[x]%2==1)
		vec.push_back(0);
	for(int i=head[x];i;i=edge[i].next){
		if(edge[i].to!=fa){
			if(!DP(edge[i].to,x))return false;
			if(dp[edge[i].to]!=-1)vec.push_back(dp[edge[i].to]+1);
		}
	}

	sort(vec.begin(),vec.end());
	if(vec.size()%2==1){
		int loc=-1;
		int l=0,r=vec.size()-1;
		while(l<=r){
			int mid=l+r>>1;
			bool jud=1;
			int p1=0,p2=vec.size()-1;
			while(p1<p2){
				if(p1==mid)p1++;
				if(p2==mid)p2--;
				if(vec[p1]+vec[p2]>limit){
					jud=0;
					break;
				}
				p1++;p2--;
			}
			if(jud){
				loc=mid;
				r=mid-1;
			}
			else
				l=mid+1;
		}
		if(loc==-1){
			return false;
		}
		dp[x]=vec[loc];
		return true;
	}
	else{
		for(int i=0,j=vec.size()-1;i<j;i++,j--){
			if(vec[i]+vec[j]>limit){
				return false;
			}
		}
		//dp[x]=-1;
		return true;
	}
}

bool check(int len){
	limit=len;
	memset(dp,0,sizeof(dp));
	return DP(1,0);
}

void solve(){
	int l=1,r=n;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			r=mid-1;
			B=mid;
		}
		else
			l=mid+1;
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
	for(int i=1;i<=n;i++){
		if(degree[i]%2==1)
			A++;
	}
	A/=2;
	solve();
	printf("%d %d\n",A,B);
	return 0;
}

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

constexpr int invalid = -2;

class square_root_decomposition {
public:
    square_root_decomposition(int N)
        : B(sqrt(N))
    {
        N = (N + B - 1) / B * B;
        before.assign(N / B, -1);
        after.assign(N / B, -1);
        donut.assign(N, 0);
    }

    void eval(int b) {
        if(before[b] == -1) {
            return;
        }

        for(int i = B * b; i < B * (b + 1); ++i) {
            if(donut[i] == before[b]) {
                donut[i] = after[b];
            } else {
                donut[i] = invalid;
            }
        }
        before[b] = after[b] = -1;
    }

    void update_block(int b, int x) {
        if(after[b] != -1) {
            if(after[b] == x - 1) {
                after[b] = x;
            } else {
                after[b] = invalid;
            }
        } else {
            before[b] = x - 1;
            after[b] = x;
        }
    }

    void update_naive(int l, int r, int x) {
        for(int i = l; i <= r; ++i) {
            if(donut[i] == x - 1) {
                donut[i] = x;
            } else {
                donut[i] = invalid;
            }
        }
    }

    void update(int l, int r, int x) {
        if(l / B == r / B) {
            eval(l / B);
            update_naive(l, r, x);
        } else {
            int bl = l / B;
            int br = r / B;
            if(l % B != 0) {
                eval(l / B);
                update_naive(l, (l + B - 1) / B * B - 1, x);
                bl++;
            }
            if(r % B != B - 1) {
                eval(r / B);
                update_naive(r - r % B, r, x);
                br--;
            }
            
            for(int i = bl; i <= br; ++i) {
                update_block(i, x);
            }
        }
    }

    int query(int k) {
        for(int i = 0; i < (int)before.size(); ++i) {
            eval(i);
        }
        return count(begin(donut), end(donut), k);
    }

    void dbg() {
        for(int i = 0; i < (int)donut.size(); ++i) {
            cout << "dbg donut: " << i << ' ' << donut[i] << endl;
        }
        for(int b = 0; b < (int)before.size(); ++b) {
            cout << "dbg block: " << b << ' ' << before[b] << ' ' << after[b] << endl;
        }
    }

private:
    const int B;
    vector<int> before, after;
    vector<int> donut;
};


int main() {
    int N, K, T;
    cin >> N >> K;
    cin >> T;

    square_root_decomposition sq(N);

    for(int i = 0; i < T; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        sq.update(l-1, r-1, x);
    }

    cout << sq.query(K) << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <iomanip>
using namespace std;
using ll = long long;
#define REP(i,N) for(ll i=0;i<N;++i)

int main() {
	ll n, m, d;
	cin >> n >> m >> d;
	double res = 0;
	if (d == 0) {
		res = 1. * (m-1)/n;
	} else {
		res = 1. * 2*(n-d)*(m-1) / (n*n);
	}
	cout << setprecision(10) << res << endl;
	return 0;
}



Measured memory_bytes: 256
#ifndef HOME
	#pragma GCC target("avx")
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("unroll-loops")
	#pragma comment(linker, "/stack:200000000")
	#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define MAX(a, b) __builtin_ia32_pmaxsd128(a, b)
#define MIN(a, b) __builtin_ia32_pminsd128(a, b)

#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;

using namespace __gnu_cxx;
using namespace __gnu_pbds;

template <class key_type>
using superTree = tree<key_type, null_type, less<key_type>, 
					   rb_tree_tag, tree_order_statistics_node_update>;
using v4si = int __attribute__ ((vector_size(16)));

const int MOD = 1000000007;

inline int _(int x, int y) {
	x += y;
	if (x >= MOD) { return x - MOD; }
	if (x < 0)    { return x + MOD; }
	return x; }

inline void __(int &x, int y) {
	x = _(x, y); }

/*
 * TO DO:
 *	
 * - long long instead of int
 * - bigger array sizes
 * - array / list instead of map / set
 * - can bruteforce with tricks pass system tests? 
 *
 * - NEVER STOP THINKING / CODING !!!
 */

const int DIM = 200005;

int arr[DIM];

bool solve(int n, int v) {
	set<pair<int, int>> mst;
	for (int i = 2; i <= n; ++i) {
		if (arr[i] > arr[i - 1]) {
			continue; }
		while (mst.size() and mst.rbegin() -> first > arr[i]) {
			mst.erase(mst.find(*mst.rbegin())); }
		for (int j = arr[i]; true; --j) {
			if (j < 1) {
				return false; }
			pair<int, int> pr;
			if (mst.size() and mst.rbegin() -> first == j) {
				pr = *mst.rbegin(); mst.erase(mst.find(pr)); }
			else {
				pr = make_pair(j, 0); }
			++pr.second;
			if (pr.second < v) {
				mst.insert(pr); break; } } 
		if (mst.size() and mst.begin() -> first < 1) {
			return false; } }
	return true; }

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#ifdef HOME
	freopen("cf.in", "r", stdin);
	freopen("cf.out", "w", stdout);
#endif		
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i]; }
	int le = 1, ri = n;
	while (le <= ri) {
		int md = (le + ri) / 2;
		if (solve(n, md)) {	
			ri = md - 1; }
		else {
			le = md + 1; } }
	cout << le;
	return 0; }


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>

using namespace std;

int n,s,memo[1024][500];
 
int search(int stat,int sum,int dep){
    if(dep==n)  return memo[stat][sum]=(s==sum);
    if(~memo[stat][sum])    return memo[stat][sum];
    if(sum>s)    return 0;
 
    int cnt=0;
    for(int i=0;i<10;i++){
        if((stat&(1<<i))==0){
            stat|=1<<i;
            cnt+=search(stat,sum+i*(n-dep),dep+1);
            stat&=~(1<<i);
        }
    }
    return memo[stat][sum]=cnt;
}

int main(){
	while(cin>>n>>s){
		if(n == 0 || s>= 1000){ puts("0"); continue;}
		memset(memo,-1,sizeof(memo));
		cout << search(0,0,0) << endl;
	}

    return 0;
}

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

int main()
{
    string s;
    cin >> s;
    bool found = 0;
    int i, j;
    for (i = 0; i < (int)s.size() - 1; i++)
    {
        for (j = i + 1; j < (int)s.size(); j++)
        {
            if (s[i] == s[j])
            {
                if (2 > (j - i + 1) / 2)
                    found = 1;
                break;
            }
        }
        if (found)
            break;
    }
    if (found)
        cout << i + 1 << " " << j + 1 << endl;
    else
        cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 3740
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	int n;
	string s;
	map<string,vector<int> > m;
	while(cin >> s >> n){
		m[s].push_back(n);
	}
	for(auto it = m.begin();it != m.end();it++){
		cout << it->first << endl;
		sort(it->second.begin(),it->second.end());
		for(int i = 0;i < it->second.size() - 1;i++) cout << it->second[i] << " ";
		cout << it->second[it->second.size() - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 3168
#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 {
        cout << "a > b" << endl;
    }
    return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

#define int long long

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

signed main(){
    int A,B;
    cin >> A >>B;
    cout << A*B/gcd(A,B)<<endl;
}

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

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

#define fr first
#define sc second

const ll mod = 1e9+7;
const int N = 3333;
const int M = 4e5+7;

/* Extended GCD + Modular inverse
 */
// Find x,y  s.t.  a x + b y = gcd(a, b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
ll invMod(ll a, ll m=mod)
{
	ll x,y;
	if(extgcd(a,m,x,y)==1) return (x+m)%m;
	return -1;
}

ll fact[M], rfact[M], dp[N];
ll pp(int a, int b)
{
  if(a < 0 || b < 0) return 0;
  return fact[a+b] * rfact[a] % mod * rfact[b] % mod; 
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  rfact[0] = invMod(fact[0] = 1);
  for(int i=1;i<M;++i)
    rfact[i] = invMod(fact[i] = fact[i-1] * i % mod);
  
  int h, w, n;
  cin >> h >> w >> n;
  vector<pii> p(n);
  for(pii& t: p)
    cin >> t.fr >> t.sc;
  p.emplace_back(1,1);
  p.emplace_back(h,w);
  n+=2;
  
  sort(p.begin(), p.end());
  
  dp[0] = mod-1;
  for(int i=1;i<n;++i)
  {
    int r = p[i].fr;
    int c = p[i].sc;
    for(int j=0;j<i;++j)
    {
      int rr = p[j].fr;
      int cc = p[j].sc;
      if(rr > r || cc > c) continue;
      
      dp[i] -= dp[j] * pp(r - rr, c - cc) % mod;
      if(dp[i] < 0) dp[i] += mod;
      if(dp[i] >= mod) dp[i] -= mod;
    }
  }
  
  cout << dp[n-1] << endl;
  
  return 0;
}


Measured memory_bytes: 6656
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = LI()
    if a[0] == a[1]:
        return a[2]
    if a[0] == a[2]:
        return a[1]

    return a[0]


print(main())




Measured memory_bytes: 7720
#include <stdio.h>
 
int main(void) {
     
    int t, n, i;
    int s, f;
    int sum;
     
    while(1){
        sum = 0;
 
        scanf("%d", &t);
        if(t == 0)  break;
         
        scanf("%d", &n);
     
        for(i = 0; i < n; i++) {
            scanf("%d%d", &s, &f);
            sum += (f - s);
        }
         
        if( t <= sum ){
            printf("OK\n");
        }else{
            printf("%d\n", (t - sum));
        }
    }  
    return 0;
}

Measured memory_bytes: 2748
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
constexpr char ln =  '\n';

const int mx=100010;
const ll mod=1e9+7;

vector<vector<vector<ld>>> dp(310, vector<vector<ld>>(310, vector<ld>(310,0)));
int n;

ld rec(int x, int y, int z){
  if(dp[x][y][z]!=0) return dp[x][y][z];
  if(x==0 && y==0 && z==0) return 0;
  ld tmp = 1.0;
  if(x>0){ tmp += rec(x-1,y+1,z)*(ld)x/n; }
  if(y>0){ tmp += rec(x,y-1,z+1)*(ld)y/n; }
  if(z>0){ tmp += rec(x,y,z-1)*(ld)z/n; }
  return dp[x][y][z] = tmp*n/(x+y+z);
}

int main(){
  cin >> n;
  vector<int> a(3,0);
  rep(i,n){
    int k; cin >> k; k--;
    a[k]++;
  }
  ld ans = rec(a[2],a[1],a[0]);
  cout << fixed << setprecision(10) << ans << ln;
  return 0;
}

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

using namespace std;

#define rep(i, x)   for (__typeof(x) i = 0; i < x; i++)
#define mp             make_pair
#define pb             push_back
#define fi             first
#define se             second
#define sz(x)          (int)((x).size())
#define all(x)         (x).begin(), (x).end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define eprintf(...)   fprintf(stderr, __VA_ARGS__)
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define repi(i, x)  for (__typeof(x) i = x-1; i >= 0; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;
typedef vector<vector<int> > vvi;
const   int            infi = numeric_limits<int>::max();
const   double         eps = 0;
const   int            ms  = 0;


vector<vector<pair<int, int>>> G;

//vector<int> vis;
vector<int> hei;
vector<int> par;
void dfs(int f, int t, int h, int i){
    //debug(f)debug(t)debug(h)debug(i)
    if(hei[t] == -1){
        hei[t] = h;
        par[t] = f;
    }
    else {
        if(h > hei[t]){
            hei[t] = h;
            par[t] = f;
        }
        else{
            if(f!=-1){
            G[f][i].second = 1;
            return;
            }
        }
    }
    for(int i = 0; i < G[t].size(); i++){
        auto nt_v = G[t][i];
        if(nt_v.second ==1)continue;
        dfs(t, nt_v.first, h+1, i);
    }
}

int main()
{
    ios::sync_with_stdio(false);//endl->"\n"
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    vi A(N-1+M), B(N-1+M);
    G = vector<vector<pair<int, int>>>(N, vector<pair<int, int>>(0));
    hei = vi(N,-1);
    par = vi(N, -1);
    vi isch(N, 0);
    rep(i, N-1+M){
        cin >> A[i] >> B[i];
        isch[B[i]-1]=1;
        G[A[i]-1].pb({B[i]-1, -1});
    }
    int root = -1;
    rep(i, N){
        if(isch[i] == 0){
            root = i;
            break;
        }
    }
    hei[0] = 0;
    dfs(-1, root, 0, 0);
    rep(i, N){
        cout << par[i]+1 << "\n";
    }
    return 0;
}

Measured memory_bytes: 12928
#include <stdio.h>
int main(){
  int s1, s2, s3, s4, x, y;
  scanf("%d %d %d %d",&s1, &s2, &s3, &s4);
  x=(s1+s2+s3+s4)/60;
  y=(s1+s2+s3+s4)%60;
  printf("%d\n",x);
  printf("%d\n",y);
 
  return 0;
}

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

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

long long MOD = 1000000000 + 7;
long long MAX = 1000000000000000000;

int main(){
  cout << setprecision(10);
  int N;
  cin >> N;
  long double T, A;
  cin >> T >> A;

  long double ans;
  long double abs_diff = 1000.0;

  for(int i = 0; i < N; i++){
    long double h;
    cin >> h;
    long double tmp_abs_diff = abs(T - 0.006 * h - A);

    if(tmp_abs_diff < abs_diff){
      abs_diff = tmp_abs_diff;
      ans = i;
    }
  }
  cout << ans+1 << endl;
}


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

int main() {

  int stop = 0;
  vector<int> x(3000);
  vector<int> y(3000);
  
  int i = 0;
  while (i<3000 && stop==0) {
    cin >> x.at(i) >> y.at(i);
    if(x.at(i) == 0 && y.at(i) == 0) {
	  stop = 1;
    } else {
	  if (x.at(i) > y.at(i)) {
        int p;
        p = x.at(i);
        x.at(i) = y.at(i);
        y.at(i) = p;
      }
      cout << x.at(i) << ' ' << y.at(i) << endl;
    }
    i++;
  }
  
  return 0;
}


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

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

using namespace std;

using ll = long long;

class binary_indexed_tree {
private:
    size_t size;
    long long *a;
public:
    binary_indexed_tree(size_t n);
    ~binary_indexed_tree();
    void add (size_t i, long long x);
    long long sum(size_t i) const;
};

binary_indexed_tree::binary_indexed_tree(size_t n) {
    size = n;
    a = new long long[n]();
}

binary_indexed_tree::~binary_indexed_tree() {
    delete [] a;
}

void binary_indexed_tree::add(size_t i, long long x) {
    for (int j = i; j < size; j |= j + 1) {
        a[j] += x;
    }
}

long long binary_indexed_tree::sum(size_t i) const {
    long long result = 0;
    for (int j = i - 1; j >= 0; j = (j & (j + 1)) - 1) {
        result += a[j];
    }
    return result;
}

template <class Iterator>
unsigned long long inversion_number(Iterator first, Iterator last) {
    using T = typename iterator_traits<Iterator>::value_type;
    size_t size = distance(first, last);
    pair<T, int> *a = new pair<T, int>[size];
    for (int i = 0; i < size; ++i) {
        a[i] = pair<T, int>(*(first + i), i);
    }
    sort(a, a + size);
    int *b = new int[size];
    for (int i = 0; i < size; ++i) {
        b[a[i].second] = i;
    }
    unsigned long long result = 0;
    binary_indexed_tree bit(size);
    for (int *it = b + size - 1; it >= b; --it) {
        result += bit.sum(*it);
        bit.add(*it, 1);
    }
    delete [] a;
    delete [] b;
    return result;
}

template <class Pred>
ll partition_point_ll(ll first, ll last, Pred p) {
    ll count = last - first;
    while (count > 0) {
        ll step = count / 2;
        ll mid = first + step;
        if (p(mid)) {
            first = mid + 1;
            count -= step + 1;
        } else {
            count = step;
        }
    }
    return first;
}



const int A_MAX = 1000000000;

ll solve(const vector<int> &a) {
    ll N = a.size();
    function<bool(int)> f = [&](int x) {
        vector<int> S(N + 1);
        S[0] = 0;
        REP(i, N) {
            if (a[i] >= x) {
                S[i + 1] = S[i] + 1;
            } else {
                S[i + 1] = S[i] - 1;
            }
        }
        ll M = (ll)N * (N + 1) / 2;
        ll C = M - inversion_number(all(S));
        return C >= (M + 1) / 2;
    };
    return partition_point_ll(0, A_MAX + 1, f) - 1;
}

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) cin >> a[i];
    cout << solve(a) << endl;
    return 0;
}

Measured memory_bytes: 3032
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const arr = input.split(" ").map(Number);
const a = arr[0];
const b = arr[1];
const c = a/b;
const d = Math.floor(c);
const r = a%b;
const f = c.toFixed(5);

console.log(d + " " + r + " " + f);



Measured memory_bytes: 15408
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, K = map(int, input().split())
L = list(map(int, input().split()))
accL = [0] + list(accumulate(L))
_pos = [l if l > 0 else 0 for l in L]
accPos = [0]+list(accumulate(_pos))
sumPos = accPos[-1]

ans = -float('inf')
for s in range(0, N-K+1):
    tmpS = accL[s+K]-accL[s]
    posS = accPos[s+K]-accPos[s]
    ans = max(ans, tmpS+sumPos-posS, sumPos-posS)
print(ans)


Measured memory_bytes: 18284
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cstring>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 110000;
void run_case()
{
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while (n)
    {
        n = n / k;
        ans++;
    }
    cout << ans << "\n";
}
int main()
{
    //检查有没有特判0,有没有越界限.
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    run_case();
    return 0;
}

Measured memory_bytes: 3652
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	m := scanInt()
	k := scanInt()

	x := n * m
	comb := CombinationInit(x, MOD)

	ans := 0
	for i := 0; i < n; i++ {
		ans += comb(x-2, k-2) * i % MOD * (n - i) % MOD * m % MOD * m % MOD
		ans %= MOD
	}
	for i := 0; i < m; i++ {
		ans += comb(x-2, k-2) * i % MOD * (m - i) % MOD * n % MOD * n % MOD
		ans %= MOD
	}

	fmt.Fprintln(wr, ans)
}

// MOD constant
const MOD = 1000000007

// CombinationInit returns a function that calculates a combinatorial in O(1). O(n)
func CombinationInit(n, p int) func(a, b int) int {
	fac := make([]int, n+1)
	ifac := make([]int, n+1)
	inv := make([]int, n+1)

	fac[0], fac[1] = 1, 1
	ifac[0], ifac[1] = 1, 1
	inv[1] = 1

	for i := 1; i < n; i++ {
		fac[i+1] = fac[i] * (i + 1) % p
		inv[i+1] = p - inv[p%(i+1)]*(p/(i+1))%p
		ifac[i+1] = ifac[i] * inv[i+1] % p
	}

	return func(a, b int) int { return (fac[a] * ifac[b] % p) * ifac[a-b] % p }
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll inf = 1e18+5;
ll n, h[200005], a[200005];
//~ struct node{
	//~ ll s, e, m, v;
	//~ node *l, *r;
	//~ node (ll _s, ll _e){
		//~ s = _s;e=_e; m=(s+e)/2;
		//~ if (s!=e){
			//~ l = new node(s, m);
			//~ r = new node(m+1, e);
			//~ v = max(l->v, r->v);
		//~ }else v = 0;
	//~ }
	//~ ll query(ll x, ll y){
		//~ if (s == x && e == y)return v;
		//~ if (x > m)return (r->query(x, y));
		//~ if (y <= m)return (l->query(x, y));
		//~ return (max(l->query(x, m), r->query(m+1, y)));
	//~ }
	//~ void update(ll x, ll val){
		//~ if (s == x && e == x){v = val; return;}
		//~ if (x > m)r->update(x, val);
		//~ else l->update(x, val);
		//~ v = max(l->v, r->v); 
	//~ }
//~ }*root;
struct node{
    ll s,e,m,v; //global variables
    node *l, *r; //global pointers
    node(ll _s, ll _e){ //init
        s=_s;e=_e;m=(s+e)/2;
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
            v=max(l->v, r->v);
        }else v=0; //starts off with 0 before any updates
    }
    
    ll query(ll x, ll y){
        if (s == x && e == y)return v; //leaf
        if (x > m)return(r->query(x, y)); //only part of right
        if (y <= m)return(l->query(x, y)); //only part of left
        return(max(l->query(x, m),r->query(m+1, y))); //in between nodes
    }
    void update(ll x, ll val){
        if (s == x && e == x){v = val;return;} //leaf node
        if (x > m)r->update(x, val); //update the right child
        else l->update(x, val); //update the left child
        v=max(l->v,r->v); //updates all above nodes when leaf is updated
    }
}*root;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	//~ ll maxhi = 0;
	for(ll i  = 1; i <= n; i++){
		cin >> h[i];
	}
	for (ll i = 1; i <= n; i++){
		cin >> a[i];
	}
	
	root = new node(0, n);
	//~ for (ll i = 1; i <= n; i++){
		//~ root->update(h[i], a[i]);
	//~ }
	//~ cout << root->query(1, n);
	//~ for (ll i= 1; i <= n; i++)cout << h[i] <<  ' ';
	//~ dp[i] stores the max sum for flower that has height h[i]
	for (ll i = 1; i<= n; i++){
		//for each flower
		//~ for (ll j = 0; j< h[i]; j++){
			//~ dp[h[i]] = max(dp[h[i]], dp[j]+h[i]);
		//~ }
		root->update(h[i], a[i]);
		ll vv = root->query(0, h[i]-1ll);
		root->update(h[i], vv+a[i]);
	}
	cout << root->query(1, n);
}


Measured memory_bytes: 28416
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp make_pair
#define sz(x) ((int)(x).size())
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) x.begin(),x.end()
#define y1 omg
#define INF 1000000010
#define FOR(x, n) for(int x=0; x<n; x++)
#define ini(x, n) memset(x, n, sizeof(x));
#define MOD (int)1e9 + 7
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;

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

string a, b;

int main() {
	cin >> a >> b;
	if (a == b.substr(0, a.size())) cout << "Yes";
	else cout << "No";
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    cout<<"ABC"<<n<<endl;
    return 0;
}


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

using namespace std;

typedef long long LL;

LL v[10];

int main()
{
	for (int i=1;i<=4;i++)scanf("%lld",&v[i]);
	LL N;
	scanf("%lld",&N);
	LL v1 = min(4*v[1],min(2*v[2],v[3]));
	LL ans = min(v1 * N, (N/2) * v[4] + (N%2) * v1);
	printf("%lld\n",ans);
}

Measured memory_bytes: 256
#include <string>
#include <iostream>

using namespace std;

int main()
{
  string s;
  cin >> s;
  char c = s[0];
  for (int i = 1; i < s.size(); ++i)
  {
    if (c != s[i])
    {
      cout << "Yes" << endl;
      return 0;
    }
    c = s[i];
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256