akhauriyash/Code-Regression huggingface dataset:
import java.io.{PrintWriter, _}
import java.util
import java.util._


object Main {
  def main(args: Array[String]): Unit = {
    val inputStream = System.in
    val outputStream = System.out
    val in = new InputReader(inputStream)
    val out = new PrintWriter(outputStream)
    val solver = new Task
    solver.solve(1, in, out)
    out.close()
  }

  class Task {
    def solve(testNumber: Int, in: InputReader, out: PrintWriter): Unit = {
      val a = in.nextInt
      val b = in.nextInt
      out.println(a * a - b)
    }
  }

  class InputReader(val stream: InputStream) extends AutoCloseable {
    //reader = new BufferedReader(new FileReader(stream), 32768);
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer = new StringTokenizer("")


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

    def nextLine: String = {
      try
        return reader.readLine
      catch {
        case e: IOException =>
          e.printStackTrace()
      }
      ""
    }

    def nextInt: Int = next.toInt

    def nextLong: Long = next.toLong

    override def close(): Unit = {
    }
  }

}


Measured memory_bytes: 27212
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
int main(){
    int n, k, d, a, ans= 0; sc(n), sc(k);
    vector<int> v(n,0);
    rep(i, 0, k){
        sc(d);
        rep(j, 0, d) sc(a), v[a-1] += 1;
    }
    rep(i, 0, n) if (v[i]==0) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3704
def root(x):
    if x == par[x]:
        return x
    par[x] = root(par[x])
    return par[x]

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

n = int(input())
par = [i for i in range(2**(n))]+[-2,-1]
rank = [0]*(2**(n)+2)
a = input()
x = [None]*(2**(n-1))
for i in range(2**(n-1)):
    x[i] = (a[2*i],a[2*i+1])
    if (a[2*i]==a[2*i+1] == "0"):
        par[2**(n-1)+i] = -1
    if (a[2*i]==a[2*i+1] == "1"):
        par[2**(n-1)+i] = -2
for i in range(2**(n-1)):
    for k in range(i+1,2**(n-1)):
        if x[i] == x[k]:
            unite(2**(n-1)+i,2**(n-1)+k)

for k in range(n-2,-1,-1):
    x = [None]*(2**k)
    for l in range(2**k):
        x[l] = (root(2**(k+1)+2*l),root(2**(k+1)+2*l+1))
        if  (root(2**(k+1)+2*l) == root(2**(k+1)+2*l+1)):
            unite(2**(k+1)+2*l,2**k+l)
    for i in range(2**(k)):
        for l in range(2**(k)):
            if i != l:
                if x[i] == x[l]:
                    unite(2**(k)+i,2**(k)+l)
p = list(set(par))
p.remove(-1)
p.remove(-2)
print(len(p)-1)



Measured memory_bytes: 5644
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        int n = in.nextInt();
        int k = in.nextInt();
        if (n==1)
            System.out.print(k);
        else
        {
            int s=k;
            for (int i=1;i<n;i++){
                s*=(k-1);
            }
            System.out.print(s);
        }
    }
}

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

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

	double sum = 0;
	for( int i = 0; i < n; ++i )
	{
		double x;
		string u;
		cin >> x >> u;
		if( u == "JPY" )
		{
			sum += x;
		}
		else
		{
			sum += x * 380000;
		}
	}

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

int main()
{
    int n,t;
    scanf("%d %d",&n,&t);
    int a[100],b[100];
    for(int i=0;i<n;i++) scanf("%d %d",&a[i],&b[i]);
    int arr[100]={};
    int tmp=0;
    for(int i=0;i<n;i++) if(b[i]<=t)arr[tmp++]=a[i];
    std::sort(arr,arr+tmp);
    if(arr[0]==0) printf("TLE\n");
    else printf("%d\n",arr[0]);
}

Measured memory_bytes: 128
import numpy as np
from numba import njit


def main(N, K, A):
    @njit(cache = True) # numpyの高速化．雲泥の差になった．知らなかった．
    def rep(N, A):
        B = np.zeros(N + 1, dtype=np.int64) # np.int64としないとnjitがエラー
        for x in range(N):
            minimum = max(0, x - A[x])
            maximum = min(N, x + A[x] + 1)
            # B[minimum:maximum] += 1   # これだと実質for文回してるような感じだから遅い？
            B[minimum] += 1
            B[maximum] -= 1
        # return B  # これだと実質for文回してるような感じだから遅い？
        return np.cumsum(B)[:-1]

    A = np.array(A, dtype=np.int64)
    for k in range(K):
        B = rep(N, A)
        if np.array_equal(A, B):
            break
        else:
            A = B
    return A



if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(' '.join([str(i) for i in main(N, K, A)]))

Measured memory_bytes: 137332
#include<bits/stdc++.h>
using namespace std;
int n;
long long a,x[51],q[51],res,dp[51][51][2501];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>a;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		q[i]=q[i-1]+x[i];
	}
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
		dp[i][0][0]=1;//no
		for(int j=1;j<=i;j++){//choose j
			for(int k=1;k<=q[i];k++){
				if(k>=x[i])//can choose,add choose
					dp[i][j][k]=dp[i-1][j-1][k-x[i]];
				dp[i][j][k]+=dp[i-1][j][k];//not choose
			}
		}
	}
	for(int i=1;i<=n;i++)
		res+=dp[n][i][i*a];
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 49024
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

int N, M, K, Q, W, H, R, C;
string S;

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int A, P;
    cin >> A >> P;
    P += A * 3;

    cout << P / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
class Dice
  def initialize(numbers)
    @numbers = numbers
    @map = {:top => 1, :R => 6, :S => 2, :E => 3, :N => 5, :W => 4}
  end

  def move(vec)
    case vec
    when "N"
      temp = @map.clone
      temp[:top] = @map[:S]
      temp[:R] = @map[:N]
      temp[:S] = @map[:R]
      temp[:N] = @map[:top]
      @map = temp.clone
    when "W"
      temp = @map.clone
      temp[:top] = @map[:E]
      temp[:R] = @map[:W]
      temp[:E] = @map[:R]
      temp[:W] = @map[:top]
      @map = temp.clone
    when "S"
      temp = @map.clone
      temp[:top] = @map[:N]
      temp[:R] = @map[:S]
      temp[:S] = @map[:top]
      temp[:N] = @map[:R]
      @map = temp.clone
    when "E"
      temp = @map.clone
      temp[:top] = @map[:W]
      temp[:R] = @map[:E]
      temp[:E] = @map[:top]
      temp[:W] = @map[:R]
      @map = temp.clone
    end
  end

  def top_number
    @numbers[@map[:top] - 1]
  end
end

dice = Dice.new(gets.split.map(&:to_i))
ins = gets

ins.length.times do |i|
  dice.move ins[i]
end

puts dice.top_number

Measured memory_bytes: 8752
/**
*    created: 21.06.2020 02:57:51
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcount(bit)
#define mod 1000000007
#define pi acos(-1.0)
using namespace std;

signed main() {

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

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int l, r;
    vector<int> made(n);
    rep(i,n) {
        if (i >= 1 && s[i] == 'C' && s[i-1] == 'A') made[i]++;
    }
    rep2(i,1,n) made[i] += made[i-1];
    rep(i,q) {
        cin >> l >> r;
        // substr(l-1,r-l+1)
        cout << made[r-1] - made[l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 4252
#include <bits/stdc++.h>
 
#define int long long
 
// loop
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 	// a ~ b-1	(ascending)
#define REP(i, n) FOR(i, 0, n)							// 0 ~ n-1
#define NREP(i, n) FOR(i, 1, n + 1)						// 1 ~ n
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)	// a ~ b	(descending)
#define RREP(i, n) RFOR(i, n, 0)						// n ~ 0
#define RNREP(i, n) RFOR(i, n, 1)						// n ~ 1
 
// container operation
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define ASORT(c) std::sort((c).begin(), (c).end())
#define DSORT(c) std::sort((c).begin(), (c).end(), std::greater<typeof((c).front())>())
#define SIZE(x) ((int)(x).size())
 
// debug
#define check(x) std::cout << #x << " = " << x << '\n'
 
// print
#define cout(x) std::cout << x << '\n'
 
// typedef
typedef std::vector<int> VI;
typedef std::vector<VI> VII;
typedef std::vector<bool> VB;
typedef std::vector<std::string> VS;

std::string yes = "Yes\n";
std::string no = "No\n";

void solve();

signed main() {
  solve();
  return 0;
}

void solve() {
  int a, b;
  std::cin >> a >> b;
  if (a <= 5) {
    cout(0);
  } else if (a >= 6 && a <= 12) {
    cout(b / 2);
  } else {
    cout(b);
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
typedef map<int, int> mii;
typedef set<int> si;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
// #define endl '\n';
#define fi first
#define se second
#define NONVOID [[nodiscard]]
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
template <class T> inline void dump(T &v){irep(i, v){cout<<*i<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

template<class T>
void lambdaSort(vector<T> &v) {
    sort(all(v), [](auto const& l, auto const& r) {
        return l.se < r.se; // このbool式が成り立つ時入れ替える
    });
}

int main() {

    int n,m;
    cin>>n>>m;
    vpii v(m);
    set<int> cut;
    rep(i,m)cin>>v[i].fi>>v[i].se;
    // lambdaSort(v);
    Sort(v);
    // rep(i,m)cout<<"==="<<v[i].fi<<" "<<v[i].se<<endl;
    int ans=0;
    int l=v[0].fi,r=v[0].se;
    for(int i=1;i<m;i++){
        // cout<<"                   "<<l <<" "<<r<<" "<<ans<<endl;
        if(l <= v[i].fi && v[i].se <= r) {
            l=v[i].fi;
            r=v[i].se;
        } else if(l <= v[i].fi && v[i].fi < r) {
            l=v[i].fi;
        } else if(l < v[i].se && v[i].se <= r) {
            r=v[i].se;
        } else {
            ans++;
            l=v[i].fi;
            r=v[i].se;
        }
    }
    fin(ans+1);
}

Measured memory_bytes: 1024
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    a = int(input())

    s = set()
    s.add(a)
    for ans in count(2):
        if a % 2 == 0:
            a //= 2
        else:
            a = 3 * a + 1
        if a in s:
            print(ans)
            break

        s.add(a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3948
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, FN) for(int i = 0; i < ( FN ); i++)
int main() {
    int n;
    cin >> n;
    vector<int> a;
    for(int i = 0; i < n; i++) {
        int hoge;
        cin >> hoge;
        a.push_back(hoge);
    }
    sort(a.begin(), a.end());
    int A = 0, B = 0;
    for(int i = 0; i < n; i++) {
        if(i % 2 == 0) A += a[n - i - 1];
        else B += a[n - i - 1];
    }
    cout << abs(A - B) << endl;
    return 0;
}


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

int main(void) {
  int x, n;
  cin >> x >> n;
  int p[n];
  rep(i, n) cin >> p[i];
  int i = 0;
  while (true) {
    int A = x - i, B = x + i;
    bool a = true, b = true;
    
    rep(i, n) {
      if (A == p[i]) {
        a = false;
      }
    }
    if (a) {
      cout << A << '\n';
      return 0;
    }

    rep(i, n) {
      if (B == p[i]) {
        b = false;
      }
    }
    if (b) {
      cout << B << '\n';
      return 0;
    }
    i++;
  }
  return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
//constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353;
constexpr int MAX = 5000000;

class UnionFind {
public:
	vector<int> Parent;
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}
	int root(int A) {
		if (Parent[A] < 0) {
			return A;
		}
		return Parent[A] = root(Parent[A]);
	}

	long long size(int A) {
		return -(long long)Parent[root(A)];
	}

	bool connect(int A, int B) {
		A = root(A);
		B = root(B);
		if (A == B) {
			return false;
		}
		if (size(A) < size(B)) {
			swap(A, B);
		}

		Parent[A] += Parent[B];
		Parent[B] = A;

		return true;
	}

};


int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n; cin >> n;
	vector<tuple<int, int, int>> vt(n);
	UnionFind uni(n);
	multiset<pair<int, int>> s1, s2;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		vt[i] = make_tuple(x, y, i);
		s2.emplace(y, i);
	}
	sort(vt.begin(), vt.end());
	for (auto [x, y, id] : vt) {
		s2.erase(s2.find({ y,id }));
		{
			auto itr = s1.lower_bound({ y,-inf });
			if (itr != s1.begin()) {
				itr = prev(itr);
				uni.connect(itr->second, id);
			}
		}
		{
			auto itr = s2.upper_bound({ y,inf });
			if (itr != s2.end()) {
				uni.connect(itr->second, id);
			}
		}
		s1.emplace(y, id);
	}
	s2.clear();
	s1.clear();
	for (auto [x, y, id] : vt) {
		s2.emplace(x, id);
	}
	sort(vt.begin(), vt.end(), [&](auto i, auto j) {
		return get<1>(i) < get<1>(j);
		});
	for (auto [x, y, id] : vt) {
		s2.erase(s2.find({ x,id }));
		{
			auto itr = s1.lower_bound({ x,-inf });
			if (itr != s1.begin()) {
				itr = prev(itr);
				uni.connect(itr->second, id);
			}
		}
		{
			auto itr = s2.upper_bound({ x,inf });
			if (itr != s2.end()) {
				uni.connect(itr->second, id);
			}
		}
		s1.emplace(x, id);
	}

	for (int i = 0; i < n; i++) {
		cout << uni.size(i) << "\n";
	}
	return 0;
}


Measured memory_bytes: 15872
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		int[] h = new int[n];
		int ans = 0;
		int count = 0;
		
		for(int i=0; i<n; i++){
		    h[i] = sc.nextInt();
		}
		
		for(int i=0; i<n-1; i++){
		    if(h[i] >= h[i+1]){
		        count++;
		        if(count > ans){
		            ans = count;
		        }
		    }else{
		        if(ans < count){
		            ans = count;
		        }
            count = 0;
		    }
		}
		
		
		System.out.println(ans);
    }
}


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

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e6 + 10, mod = 1e9 + 7;

int fact[N], inv[N];
ll dp[N];

int power(int a, int b)
{
	if(b == 0) return 1;
	ll res = power(a, b/2);
	res *= res, res %= mod;
	if(b & 1) res *= a, res %= mod;
	return res;
}

int comb(int n, int k)
{
	if(k < 0 || k > n) return 0;
	ll res = fact[n]; res *= inv[k], res %= mod;
	res *= inv[n - k], res %= mod; 
	return res;
}

int main()
{
	int n; cin >> n;
	if(n == 2) return cout << 1 << endl, 0;

	fact[0] = 1;
	for (int i=1; i<N; i++)
		fact[i] = 1LL * fact[i - 1] * i % mod;

	inv[N - 1] = power(fact[N - 1], mod - 2);
	for (int i=N-2; i>=0; i--)
		inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
	
	for (int i=2; i<n; i++)
	{
		int p = n - i - 1;
		int k = n - 3;
		dp[i] = comb(k + 1 - p, p);
		dp[i] *= fact[i], dp[i] %= mod;
		dp[i] *= fact[n - i - 1], dp[i] %= mod;
	}

	ll ans = 0;
	for (int i=2; i<n; i++)
	{
		ll w = dp[i] + mod - dp[i - 1]; w %= mod;
		ans += 1LL * w * i % mod, ans %= mod;
	}

	cout << ans << endl;

}


Measured memory_bytes: 15872
N,M,C=(map(int,input().split()))

B=[input().split() for i in range(N+1)]

T=0
b=B.pop(0)



for a in range(N):

    su=0+C
    for c in range(M):
        x=int(B[a][c])*int(b[c])
        su+=x

        if c+1==M:
            if su>0:
                T=T+1
print(T)


Measured memory_bytes: 3060
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "a", long, "b");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    long h, w;
    scan(h, w);
    auto wall = new string[](h);
    foreach (ref e; wall)
    {
        e = sread();
    }
    // wall.writeln();
    bool ok = true;
    foreach (i; iota(h))
    {
        foreach (j; iota(w))
        {
            if (wall[i][j] == '#')
            {
                ok &= canpaint(wall, i, j);
            }
        }
    }
    if (ok)
        writeln("Yes");
    else
        writeln("No");
}

bool canpaint(ref string[] wall, long i, long j)
{
    bool ret;
    // i.write(" "), j.writeln();
    if (i - 1 >= 0)
        ret |= (wall[i - 1][j] == '#');
    if (i + 1 < wall.length)
        ret |= (wall[i + 1][j] == '#');
    if (j - 1 >= 0)
        ret |= (wall[i][j - 1] == '#');
    if (j + 1 < wall[i].length)
        ret |= (wall[i][j + 1] == '#');

    return ret;
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
#define INFTY 1<<20
typedef long long int ll;
const int MOD=1000000007;
using Graph = vector<vector<int>>;
using ipair = pair<ll,ll>;
bool operator< (const ipair a, const ipair b){return a.first < b.first;};
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
  int n;cin>>n;
  priority_queue<ipair, std::vector<ipair>, std::less<ipair>> que1,que2;
  vector<ll> u(100002,0),v(100002,0);
  rep(i,n){
    ll num;cin>>num;
    if(i%2==0){
      v[num]++;
    }
    else{
      u[num]++;
    }
  }
  rep(i,100002){
    que1.push(make_pair(v[i],i));
    que2.push(make_pair(u[i],i));
  }
  ll ans = n;
  ipair q11,q12,q22,q21;
  q11=que1.top();q21=que2.top();
  que1.pop();que2.pop();
  q12=que1.top();q22=que2.top();
  if(q11.second!=q21.second){
    ans -= q11.first;
    ans -= q21.first;
  }
  else {
    ll mx = max(q12.first+q21.first,q11.first+q22.first);
    ans -= mx;
  }

  cout<<ans;
  return 0;
}

Measured memory_bytes: 5100
S=input()
N=len(S)
if S[0]!='A':
    print('WA')
else:
    cnt = 0
    for i in range(2,N-2+1):
        if S[i]=='C':
            cnt += 1
    if cnt != 1:
        print('WA')
    else:
        D=(S[0].isupper()>0)
        flg=0
        for i in range(1,N):
            if D==(S[i].isupper()>0):
                flg+=1
        if flg==1:
            print('AC')
        else:
            print('WA')

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    int l, i=0, a[n];
    int f = 0;
    int r = 0;
    while(cin>>l){
        a[i] = l;
        i++;
    }
    
    while(f == 0) {
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 1) {
                f = 1;
            }
        }
        if (f == 0){
            for (int i = 0; i < n; i++) {
                a[i] /= 2;  
            }
            r++;
        }
    }
    cout << r;
}


Measured memory_bytes: 3596
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	Main(BufferedReader in) throws IOException {
		int a = Integer.parseInt(in.readLine());
		int result = a + a * a + a * a * a;
		System.out.println(result);
	}

	void calc() {
	}

	void showResult() {
	}
}

Measured memory_bytes: 32628
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

int main(){
	
	int k,q;
	cin>>k>>q;
	vector<int> d(k);
	for(int i=0;i<k;i++)cin>>d[i];
	
	for(int i=0;i<q;i++){
		long long n,x,m;
		cin>>n>>x>>m;
		
		x%=m;
		long long S = 0;
		for(int j=0;j<k;j++){
			S += (long long)d[j]%m;
			if(d[j]%m==0)S+=m;
		}
		x += S * ((n-1)/k);
		for(int j=0;j<(n-1)%k;j++){
			x += (long long)d[j]%m;
			if(d[j]%m==0)x+=m;
		}
		
		cout<<n-1-x/m<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h[100005], dp[100005];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    cin >> h[i];
  dp[1] = 0, dp[2] = abs(h[2] - h[1]);
  for (int i = 3; i <= n; i++) {
    dp[i] = 0x3f3f3f3f;
    for (int j = 1; j <= k && i - j >= 1; j++) {
      dp[i] = min(dp[i - j] + abs(h[i] - h[i - j]), dp[i]);
    }
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 1792
n, m = map(int, input().split())
s = set()
t = set()
for i in range(m):
    a, b = map(int, input().split())
    if a > b : a, b = b, a
    if a == 1:
        s.add(b)
    if b == n:
        t.add(a)

if s & t:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 19024
#include <iostream>
using namespace std;
#define MAX 100000

int parent(int i) { return i / 2; }
int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }

int main() {
	int H, A[MAX + 1];
	cin >> H;

	for (int i =1;i <= H;i++)  cin >> A[i];
	for (int i =1;i <= H;i++) {
		cout << "node " << i << ": key = " << A[i] << ", ";
		if (parent(i) >= 1) cout << "parent key = " << A[parent(i)] << ", ";
		if (left(i) <= H) cout << "left key = " << A[left(i)] << ", ";
		if (right(i) <= H) cout << "right key = " << A[right(i)] << ", ";
		cout << endl;
	}
	return 0;
}


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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int maxn = 3000+10;
const ll oo = 1ll<<60;
int N,M,K,A[maxn][maxn];
ll memo[maxn][maxn][5];

ll dp(int i,int j,int cnt){
	if(i >= N || j >= M || cnt >= 4)return -oo;
	if(i == N-1 && j == M-1){
		int add = (A[i][j] != 0);
		if(cnt+add <= 3){
			return A[i][j];
		}
		return 0;
	}
	ll &res = memo[i][j][cnt];
	if(res != -1)return res;
	res = -oo;
	
	int add = (A[i][j] != 0);
	
	if(add){
		// derecha
		res = max(res,A[i][j]+dp(i,j+1,cnt+add));
		res = max(res,dp(i,j+1,cnt));
		
		//Abajo
		if(cnt+add <= 3)res = max(res,A[i][j]+dp(i+1,j,0));
		res = max(res,dp(i+1,j,0));
		
	}else{
		res = max(res,dp(i,j+1,cnt));
		res = max(res,dp(i+1,j,0));
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	forn(i,0,maxn)forn(j,0,maxn)forn(k,0,5)memo[i][j][k] = -1;
	cin >> N >> M >> K;
	forn(i,0,K){
		int r,c,v; cin >> r >> c >> v; r--; c--;
		A[r][c] = v;
	}
	ll res = dp(0,0,0);
	cout << res << '\n';
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


Measured memory_bytes: 393404
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	x := make([]int, n)
	y := make([]int, n)

	for i := 0; i < n; i++ {
		fmt.Scan(&x[i], &y[i])
	}
	sd := float64(0)
	for i := 0; i < n - 1; i++ {
		for j := i + 1; j < n; j++ {
			dx := float64(x[j] - x[i])
			dy := float64(y[j] - y[i])
			sd += math.Sqrt(dx * dx + dy * dy)
		}
	}
	fmt.Println(sd * 2 / float64(n))
}


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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int r;
int w_1, h_1, x_1, y_1;
int w_2, h_2, x_2, y_2;
int g1[505][505], g2[505][505];

bool check(int y, int x, int h, int w) {
    if ((0 <= y && y < h) && (0 <= x && x < w)) return true;
    return false;
}

vector<int> search(int sy, int sx, int h, int w, int g[505][505]) {
    priority_queue<pipii, vector<pipii>, greater<pipii>> pq;
    pq.push(make_pair(1LL, make_pair(sy, sx)));
    bool visited[h + 5][w + 5] = {};
    vector<int> cnt;
    cnt.pb(0);
    int now_level = 1;
    visited[sy][sx] = true;
    while (!pq.empty()) {
        pipii p = pq.top();
        pq.pop();
        int level = p.fi;
        int y = p.se.fi;
        int x = p.se.se;
        if (now_level < level) {
            cnt.pb(level);
            now_level = level;
        }
        else {
            cnt.pb(now_level);
        }
        rep(i, 4) {
            int ny = y + dy4[i];
            int nx = x + dx4[i];
            if (!check(ny, nx, h, w) || visited[ny][nx]) continue;
            pq.push(make_pair(g[ny][nx], make_pair(ny, nx)));
            visited[ny][nx] = true;
        }
    }
    return cnt;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> r;
    while (r != 0) {
        cin >> w_1 >> h_1 >> x_1 >> y_1;
        x_1--;y_1--;
        rep(i, h_1)rep(j, w_1) cin >> g1[i][j];
        cin >> w_2 >> h_2 >> x_2 >> y_2;
        x_2--;y_2--;
        rep(i, h_2)rep(j, w_2) cin >> g2[i][j];
        vector<int> cnt1 = search(y_1, x_1, h_1, w_1, g1);
        vector<int> cnt2 = search(y_2, x_2, h_2, w_2, g2);
        int ans = 1e12;
        rep(i, r + 1) {
            if (cnt1.size() <= i) break;
            if (cnt2.size() <= r - i) continue;
            ans = min(ans, cnt1[i] + cnt2[r - i]);
        }
        cout << ans << endl;
        cin >> r;
    }
}

Measured memory_bytes: 12924
#include<bits/stdc++.h>
#define foru(a,b,c) for(int a=b;a<=c;++a)

int n,a[21],c[21];
int re;

main()
{
    std::cin>>n;
    foru(i,1,n) std::cin>>a[i];
    foru(i,1,n) std::cin>>c[i];
    foru(i,1,n)
    {
        if(a[i]<c[i]) continue;
        else re+=(a[i]-c[i]);
    }
    std::cout << re;
}

Measured memory_bytes: 256
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }


int main() {

	ll N;	
	cin >> N;

	vll a(N), b(N);
	rep(i, N) cin >> a[i];
	rep(i, N) cin >> b[i];
	sort(all(a)), sort(all(b));

	ll ans = 0, t = 1;
	rep(k, 30) {
		vll c(N), d(N);
		rep(i, N) {
			c[i] = a[i] % (2 * t);
			d[i] = b[i] % (2 * t);
		}
		sort(all(c)), sort(all(d));

		ll cnt = 0;
		rep(j, N) {
			cnt += lower_bound(d.begin(), d.end(), 2 * t - c[j]) - lower_bound(d.begin(), d.end(), t - c[j])
				+ (d.end() - lower_bound(d.begin(), d.end(), 3 * t - c[j]));
		}

		if (cnt % 2 == 1) ans += t;
		t *= 2;

	}
	cout << ans << endl;
}

Measured memory_bytes: 6552
import java.util.Scanner;

public class Main {

	public static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] S = new int[n];
		for(int i = 0; i < n; i++) {
			S[i] = sc.nextInt();
		}
		sc.close();

		mergeSort(S, n, 0, n);
		for(int i = 0; i < n; i++) {
			if(i != S.length - 1) {
				System.out.print(S[i] + " ");
			}else {
				System.out.print(S[i]);
			}
		}
		System.out.println();
		System.out.println(count);

	}

	public static void merge(int[] A, int n, int left, int mid, int right) {
		int n1 = mid -left;
		int n2 = right - mid;
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];
		for(int i = 0; i < n1; i++) {
			L[i] = A[left + i];
		}
		for(int i = 0; i < n2; i++) {
			R[i] = A[mid + i];
		}
		L[n1] = R[n2] = Integer.MAX_VALUE;
		int x = 0;
		int y = 0;
		for(int k = left; k < right; k++) {
			count++;
			if(L[x] <= R[y]) {
				A[k] = L[x++];
			}else {
				A[k] = R[y++];
			}
		}
	}
	public static void mergeSort(int[] A, int n, int left, int right) {
		if(left + 1 < right) {
			int mid = (left + right) / 2;
			mergeSort(A, n, left, mid);
			mergeSort(A, n, mid, right);
			merge(A, n, left, mid, right);
		}
	}

}



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

int main() {
  double A,B,C,D;
 cin>>A>>B>>C>>D;
 double X=ceil(C/B),Y=ceil(A/D);
  if(X<=Y){
    cout<<"Yes"<<endl;}
    else{
      cout<<"No"<<endl;
    }
  }






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

int main()
{
  int64_t N;
  cin >> N;
  vector<int64_t> A(3 * N);
  for (int64_t i = 0; i < 3 * N; i++)
  {
    cin >> A.at(i);
  }
  int64_t lsum = 0, rsum = 0;
  multiset<int64_t> rused, lused, rremoved;
  for (int64_t i = 0; i < N; i++)
  {
    lsum += A.at(i);
    lused.insert(A.at(i));
  }
  for (int64_t i = N; i < 3 * N; i++)
  {
    rsum += A.at(i);
    rused.insert(A.at(i));
  }
  while (rused.size() > N)
  {
    rremoved.insert(*rused.rbegin());
    rsum -= *rused.rbegin();
    rused.erase(rused.find(*rused.rbegin()));
  }
  int64_t ans = lsum - rsum;
  for (int64_t i = N; i < 2 * N; i++)
  {
    lsum += A.at(i);
    lused.insert(A.at(i));
    lsum -= *lused.begin();
    lused.erase(lused.find(*lused.begin()));
    if (rused.find(A.at(i)) != rused.end())
    {
      rused.erase(rused.find(A.at(i)));
      rsum -= A.at(i);
      rused.insert(*rremoved.begin());
      rsum += *rremoved.begin();
      rremoved.erase(rremoved.find(*rremoved.begin()));
    }
    else
    {
      rremoved.erase(rremoved.find(A.at(i)));
    }
    ans = max(ans, lsum - rsum);
  }
  cout << ans << endl;
}

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

using I = long long;

vector<I> prime_factor(I n) {
  vector<I> prime;
  for(I i = 2; i <= n / i; ++i)
    for(; n % i == 0; n /= i)
      prime.emplace_back(i);
  if(n != 1) prime.emplace_back(n);
  return prime;
}

int main() {
  I N, M;
  cin >> N >> M;

  set<I> dp;
  dp.emplace(1);

  for(auto p: prime_factor(M)) {
    auto dup = dp;
    for(auto i: dup) if(i*p <= M/N) dp.emplace(i*p);
  }
  cout << *rbegin(dp) << endl;
}


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

using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define endl '\n'
#define snd second
#define fst first
#define fastio cin.tie(NULL),cout.sync_with_stdio(true)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector <int> vi;
typedef pair <int, int> ii;

const ll mod = 1e9 + 7;
const ll INF = (1LL<<50);
const double EPSILON = 0.001;
const int N = 2005;
int main(){
	fastio;
	string s;
	cin >> s;
	if(s[sz(s)-1] == 's'){
		cout << s <<"es\n";
	}else
	cout << s <<"s" << '\n';
	return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;


int main(){
    vector<char> S1, S2;
    string S, T; cin >> S >> T;
    int n = min(S.size(), T.size());
    for(auto s : S) S1.push_back(s);
    for(auto s : T) S2.push_back(s);
    sort(S1.begin(), S1.end());
    sort(S2.rbegin(), S2.rend());
    string S3="", S4 = "";
    for(auto s : S1) S3+=s;
    for(auto s : S2) S4+=s;
    if(S3 >= S4)cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
W,H,N=map(int,input().split())
xya = [tuple(map(int,input().split())) for _ in range(N)]
b = [[0]*(W) for _ in range(H)]

for x,y,a in xya:
    if a==1:
        for i in range(x):
            for j in range(H):
                b[j][i]=1
    elif a==2:
        for i in range(x,W):
            for j in range(H):
                b[j][i]=1
    elif a==3:
        for i in range(y):
            for j in range(W):
                b[i][j]=1
    else:
        for i in range(y,H):
            for j in range(W):
                b[i][j]=1
res = H*W
for row in b:
    res -= sum(row)
print(res)



Measured memory_bytes: 3064
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cout << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cout << e << " "; } cout << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

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

const string YES = "Yes";
const string NO = "No";



// ***************************************

int main(){

    string S;
    cin >> S;
    for(auto& s: S){
        if (s == '7'){
            cout << YES << endl;
            return 0;
        }
    }

    cout << NO << endl;

    return 0;
}


Measured memory_bytes: 3628
//Code by : Abhishek Tiwari
//codechef.com/users/devil_within || hackerearth.com/@devil_within
#include<bits/stdc++.h>
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long int 
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define repr(i,a,b) for(int i=(a);i>(b);--i)
#define all(v) (v).begin(),(v).end()
#define mp make_pair
#define pb push_back
#define pf push_front
#define pii pair<int,int> 
#define ff first
#define ss second 
#define mod 1000000007
#define inf 1000000000
#define gcd __gcd
#define lcm(a,b) ((a)*(b))/gcd(a,b)
using namespace std;

/*******************************************************************************************/
/*******************************************************************************************/
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { 
    os<<"["; for(int i=0;i<v.size()-1; ++i)os<<v[i]<<", ";os<<v[v.size()-1]<<"]\n"; return os; 
} 
template <typename T> ostream& operator<<(ostream& os, const set<T>& v) { 
    os<<"{"; for(auto it : v) { os<<it; if(it!=*v.rbegin()) os<<", "; } os<<"}\n"; 
    return os; 
}
template <typename T, typename S> ostream& operator<<(ostream& os, const map<T, S>& v) { 
    os<<"{"; for(auto it:v){ os<<"("<<it.first<<" : "<<it.second<<")"; if(it!=*v.rbegin()) os<<", "; } os<<"}\n"; 
    return os; 
}
template <typename T, typename S> ostream& operator<<(ostream& os, const pair<T, S>& v) { 
    os<<"("; os<<v.first<<", "<< v.second<<")"; 
    return os; 
} 
template<typename T> T maxi(T a,T b){return a>b ? a:b;}
template<typename T> T mini(T a,T b){return a<b ? a:b;}
/*******************************************************************************************/
/*******************************************************************************************/
int fpow(int x, int y, int p); 

int dfs(int src , vector<vector<int>> &adj , vector<int> &dp)
{
    if(dp[src]!=-1)
        return dp[src];
    dp[src] = 0;
    for(auto i : adj[src])
        dp[src] = max( dp[src] , 1 + dfs(i , adj , dp));
    return dp[src];
}
int32_t main()  
{
#ifndef ONLINE_JUDGE
//freopen("input.txt" , "r" , stdin);freopen("output.txt" , "w" , stdout);freopen("error.txt" , "w" , stderr);
#endif
fio;
int tcases = 1;
//cin>>tcases;
for(int tcase = 1 ; tcase <= tcases ; ++tcase)
{
    int n , m;
    cin>>n>>m;
    vector<vector<int>> adj(n+1);
    int x ,y ;
    rep(i , 0 , m)
    {
        cin>>x>>y;
        adj[x].pb(y);
    }
    vector<int> dp(n+1 , -1);
    rep(i , 1 , n+1)
        if( dp[i] == -1 )
            dfs( i , adj , dp);
    cout<< *max_element( all(dp));
    //cout<<"Case #"<<tcase<<": ";
}
return 0;
}



//Functions 

int fpow(int x, int y, int p) { 
    int res = 1; 
   x = x % p;  
   while (y > 0) { 
     if (y & 1) 
        res = (res * x) % p; 
     y = y >> 1; 
        x = (x * x) % p; 
    } 
    return res; 
} 


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

int main(){
  int n;
  cin >> n;
  
  int a, b, c, d;
  
  a = n / 1000;
  b = (n - a * 1000) / 100;
  c = (n - a * 1000 - b * 100) / 10;
  d = (n - a * 1000 - b * 100 - c * 10);
  
  if(a == b && b == c){
    cout << "Yes" << endl;
  }else if(b == c && c == d){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
T1, T2, A1, A2, B1, B2 = map(int, open(0).read().split())
P = (A1-B1)*T1
Q = (A2-B2)*T2
if P>0:
  P *= -1
  Q *= -1
if P+Q<0:
  print(0)
elif P+Q==0:
  print('infinity')
else:
  S,T = divmod(-P,P+Q)
  if T!=0:
    print(S*2+1)
  else:
    print(S*2)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF (int)1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second

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

signed main(){
	ll l,n,memo = LINF,memo2 = LINF,sum = 0;
	cin >> n >> l;
	
	rep(i,0,n){
		sum += l+i;
		if(abs(memo) > abs(l+i)){
			memo = l+i;
		}
	}
	
	cout << sum - memo << endl;
	
	
    return 0;
}

Measured memory_bytes: 256
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = map(int, input().split())
A = list(map(int, input().split()))

def rec(i, is_same):
    res = 0
    x, y = 0, 0
    for a in A:
        x += 0 ^ (a >> i & 1)
        y += 1 ^ (a >> i & 1)
    if K >> i & 1 == 0 and is_same:
        res = rec(i - 1, is_same) + x
    else:
        res = max(rec(i - 1, False) + x, rec(i - 1, True) + y)
    return res

def f(n):
    res = 0
    while n > 0:
        res += 1
        n //= 2
    return res

dp = [[-1 for _ in range(2)] for _ in range(50)]
d = 48
dp[d + 1][0] = 0
for i in range(d, -1, -1):
    x, y = 0, 0
    for a in A:
        x += 0 ^ (a >> i & 1)
        y += 1 ^ (a >> i & 1)
    x <<= i
    y <<= i

    if dp[i + 1][1] >= 0:
        dp[i][1] = max(dp[i][1], dp[i + 1][1] + max(x, y))
    if dp[i + 1][0] >= 0:
        if K >> i & 1 == 0:
            dp[i][0] = max(dp[i][0], dp[i + 1][0] + x)
        else:
            dp[i][1] = max(dp[i][1], dp[i + 1][0] + x)
            dp[i][0] = max(dp[i][0], dp[i + 1][0] + y)
    # if K >> i & 1 == 0:
    #     if (1 << i) <= K:
    #         dp[i][1] = dp[i + 1][1] + x
    #         dp[i][0] = max(dp[i + 1][0] + x, dp[i + 1][0] + y)
    #     else:
    #         dp[i][1] = dp[i + 1][1] + x
    #         dp[i][0] = dp[i + 1][0] + x
    #          # max(dp[i + 1][0] + x, dp[i + 1][1] + x)
    # else:
    #     if (1 << i) <= K:
    #         dp[i][1] = dp[i + 1][1] + y
    #         dp[i][0] = max(dp[i + 1][1] + x, dp[i + 1][0] + x, dp[i + 1][0] + y)
    #     else:
    #         dp[i][1] = dp[i + 1][1] + x
    #         dp[i][0] = dp[i + 1][0] + x
    #         # dp[i][1] = 0
    #         # dp[i][0] = 0 #max(dp[i + 1][1] + x, dp[i + 1][0] + x)
print(max(dp[0][0], dp[0][1]))


    

Measured memory_bytes: 82876
#import random
#basball
ineng = int(input())
#ivent_list = [random.randint(0,3) for _ in range(ineng)]
for _ in range(ineng):
    out_count = 0
    runner =0
    score = 0
    while out_count <3:
        event = input()
        if event == "HIT":
            runner +=1
            if runner >=4:
                score +=1
                runner = 3
                
        elif event == "HOMERUN":
            score += (runner + 1)
            runner = 0
        else:
            out_count +=1

    print(score)
            


Measured memory_bytes: 5584
#include <bits/stdc++.h>
#define N 100010
#define int long long
using namespace std;
typedef pair<int,int> P;
int n,m;
vector<int> G[N];
int flag;
int col[N];
 
P cnt;
void dfs(int pos,int c){
  if(col[pos]!=-1 && c!=col[pos]) flag = 1;
  if(col[pos]!=-1 && c==col[pos]) return; 
  if(flag) return;
  c? cnt.first++:cnt.second++;
  col[pos] = c;
  for(int nx:G[pos])dfs(nx,!c);
}
 
map<int,int> A;

int calc(int d){
  int a = (n-d)/2;
  int b = n - a;
  return a*b;
}

int dp[N] = {};
int DP(){
  int sum = 0;
  for(P a:A) sum+=a.first*a.second;

  for(P a:A){
    dp[0] = 1;
    for(int j=0;j<N;j++)if(dp[j]) dp[j] = a.second+1;
    for(int j=0;j<N;j++){
      if(j+a.first>=N)break;
      if(dp[j] == 0)continue;
      dp[j+a.first] = max(dp[j+a.first],dp[j] - 1);
    }
  }
  
  int res = 0;
  for(int i=0;i<N;i++)
    if(dp[i]>0) res = max(res,calc(abs(i-(sum-i))));
  return res;
}

signed main(){
  cin>>n>>m;
  for(int i=0,a,b;i<m;i++){
    cin>>a>>b;a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
 
  memset(col,-1,sizeof(col));
  for(int i=0;i<n;i++) {
    if(col[i]!=-1)continue;
    cnt = P(0,0); 
    dfs(i,0);
    A[abs(cnt.first-cnt.second)]++;
  }

  if(flag) cout<<"-1"<<endl,exit(0);
  cout<<DP()-m<<endl;
  return 0;
}

Measured memory_bytes: 11268
#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
	int n,k;
  	long count=0;
  	cin >> n >> k;
  	int x[n],i;
  	for(i=0;i<n;i++){
    	cin >> x[i];
    }
  	sort(x,x+n,[](int aa, int bb) {
        return aa > bb;   
    });
  	for(i=k;i<n;i++){
      	count += x[i];
    }
  	cout << count << endl;
}



Measured memory_bytes: 1024