akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int a, b, c;
    ll k;
    cin >> a >> b >> c >> k;
    int ans = a - b;
    if (k % 2 == 1) ans *= -1;
    cout << ans << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};
int main(void){
  int N;
  cin >> N;
  vector <int> X(N);
  rep(i,N) cin >> X[i];
  int ans = inf;  //体力の総和の最小値
  for (int i = 1; i <= 100; i++){
    int sum = 0;
    rep(j,N) sum += (X[j] - i) * (X[j] - i);
    ans = min(ans, sum);
  }
  cout << ans << endl;
  return 0;
}


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

void monsters()
{
	int h1,s1,h2,s2;
	cin>>h1>>s1>>h2>>s2;
	bool turn=true;
	while (h1>0 && h2>0)
	{
		if (turn)
		{
			h2=h2-s1;
		}

		else
		{
			h1=h1-s2;
		}

		turn=!turn;
	}

	if (h1>0)
	{
		cout<<"Yes"<<endl;
	}

	else
	{
		cout<<"No"<<endl;
	}
}

void goats()
{
	int s,w;
	cin>>s>>w;
	if (s>w)
	{
		cout<<"safe"<<endl;
	}	

	else
	{
		cout<<"unsafe"<<endl;
	}

}
int main()
{
	//goats();
	monsters();
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(){
    
    int A,B,X;
    cin>>A>>B>>X;
    if(A>X){
        cout<<"NO"<<endl;
        return 0;
    }

    if(A+B<X){
        cout<<"NO"<<endl;
        return 0;
    }

    if(A+B>=X){
        cout<<"YES"<<endl;
        return 0;
    }


    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265


int n,m;
vector<int> v[1000000];
vector<int> p;
bool a[1000000]={};

bool search(){

  rep(i,v[p[0]].size()){
    if(!a[v[p[0]][i]]){
      p.insert(p.begin(),v[p[0]][i]);
      return false;
    }
  }
  rep(i,v[p[p.size()-1]].size()){
    if(!a[v[p[p.size()-1]][i]]){
      p.insert(p.end(),v[p[p.size()-1]][i]);
      return false;
    }
  }


  return true;

}

int main(){
  cin>>n>>m;
  rep(i,m){
    int b,c;
    cin>>b>>c;
    v[b].push_back(c);
    v[c].push_back(b);
    if(i==0){
      p.push_back(b);
      p.push_back(c);
    }
  }

  while(1){
    a[p[0]]=true;
    a[p[p.size()-1]]=true;
    if(search()){
      cout<<p.size()<<endl;
      rep(i,p.size()){
        if(i!=0) cout<<' ';
        cout<<p[i];
      }
      cout<<endl;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 28024
#include<iostream>
using namespace std;
char a;
char x[205];
int p=0;
int main() {
	while(cin>>a) {
		if(a!='B') {
			x[++p]=a;
		} 
		if(a=='B') if(p) --p; 
	}
	for(int i=1;i<=p;i++) cout<<x[i];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF=2e18;

ll A,B,Q;
ll s[100010];
ll t[100010];
ll sToNearT[100010];
ll tToNearS[100010];
void SetNear(ll a[],ll aSize,ll b[],ll bSize,ll ans[]){
    ll previous=1;
    for(ll i=1;i<=aSize;i++){
        ans[i]=INF;
        for(ll j=previous;(b[j-1]<=a[i] && j<=bSize);j++){
            if(ans[i] > abs(b[j]-a[i])){
                ans[i]=abs(b[j]-a[i]);
                previous=j;
            }
        }
    }
}
ll Dist(ll a[],ll size,ll toNear[],ll x){
    ll index=lower_bound(a+1,a+1+size,x)-a;
    if(index>size)index--;
    // cout<<"index:"<<index<<endl;
    ll tmp=abs(x-a[index])+toNear[index];
    // cout<<"abs(x-a[index]):"<<abs(x-a[index])<<endl;
    if(index==1)return tmp;
    index--;
    return min(tmp,abs(x-a[index])+toNear[index]);
}
int main(){
    cin>>A>>B>>Q;
    s[0]=-INF;
    for(ll i=1;i<=A;i++){
        cin>>s[i];
    }
    t[0]=-INF;
    for(ll i=1;i<=B;i++){
        cin>>t[i];
    }
    SetNear(s,A,t,B,sToNearT);
    SetNear(t,B,s,A,tToNearS);
    /* for(ll i=1;i<=A;i++){
        cerr<<sToNearT[i]<<" ";
    }cerr<<endl;
    for(ll i=1;i<=B;i++){
        cerr<<tToNearS[i]<<" ";
    }cerr<<endl; */
    for(ll i=0;i<Q;i++){
        ll x;
        cin>>x;
        // cout<<"Dist:"<<Dist(t,B,tToNearS,x)<<endl;
        cout<<min(Dist(s,A,sToNearT,x),Dist(t,B,tToNearS,x) )<<endl;
    }
    return 0;
}

Measured memory_bytes: 4480
#include <stdio.h>

long long max(long long a, long long b) {
	return a > b ? a : b;
}

long long min(long long a, long long b) {
	return a < b ? a : b;
}

int main() {
	long long h, w, i, x, y, z, a;
	int ans;

	scanf("%lld%lld", &h, &w);
	if (h % 3 == 0 || w % 3 == 0) {
		printf("0\n");
		return 0;
	}
	ans = min(h, w);
	for (i = 1; i < w; i++) {
		x = h * i;
		y = (w - i) * ((h + 1) / 2);
		z = (w - i) * (h / 2);
		a = max(x, max(y, z)) - min(x, min(y, z));
		if (ans > a)
			ans = a;
	}
	for (i = 1; i < h; i++) {
		x = w * i;
		y = (h - i) * ((w + 1) / 2);
		z = (h - i) * (w / 2);
		a = max(x, max(y, z)) - min(x, min(y, z));
		if (ans > a)
			ans = a;
	}
	printf("%d\n", ans);
	return 0;
}


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

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

	int a,b;
	cin >> a >> b;

	string u;
	cin >> u;

	if (u == s)	a--;
	if (u == t)	b--;

	cout << a << " "<<b<< endl;



}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

  while(n--){
    string s;
    getline(cin,s);
    while(s.find("Hoshino") != string::npos)
      s.replace(s.find("Hoshino"), 7, "Hoshina");
    cout << s << endl;
  }

  return 0;
}

Measured memory_bytes: 1216
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kishan Sairam Adapa
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define ll long long int
#define MOD ((int)(1e9) + 7)

using namespace std;

class CPrison {
public:
    void solve(istream& cin, ostream& cout) {
        int n, m;
        cin >> n >> m;
        vector<int> g(n+2, 0);
        for(int i=0; i<m; i++) {
            int l, r;
            cin >> l >> r;
            g[l] += 1; g[r+1] += -1;
        }
        ll cnt = 0; ll run = 0;
        for(int i=1; i<=n; i++) {
            run += g[i];
            if(run == m) cnt++;
        }
        cout << cnt << '\n';
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    CPrison solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int mini = Inf;
    vector<int> w(n);
    int a, b;
    rep(i, n) {
      cin >> w[i];
    }
    rep(i, n) {
      int a = 0;
      int b = 0;
      FOR(j, 0, i + 1) {
        a += w[j];
      }
      for (int j = n - 1; j > i; --j) {
        b += w[j];
      }
      mini = min(mini, abs(a - b));
    }

    cout << mini << '\n';

    return 0;
}


Measured memory_bytes: 256
readint()=parse.(Int,readline())
function check(n)
    Nmax=100
    ff=zeros(Int,n)
    for x in 1:Nmax,y in 1:Nmax,z in 1:Nmax
        s=x^2+y^2+z^2+x*y+y*z+z*x
        if s<=n
            ff[s]+=1
        end
    end
    for i in 1:n
        println(ff[i])
    end
end
check(readint())

Measured memory_bytes: 165784
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())

    n = int(N ** 0.5)
    for i in range(n, 0, -1):
        d, m = divmod(N, i)
        if not m:
            print(d + i - 2)
            break


main()


Measured memory_bytes: 3060
using System;
using System.Collections.Generic;

class Q2
{
    static void Main(String[] args)
    {
        String str = Console.ReadLine();
        int n = int.Parse(str);
        int ans = 0,l,r;
        for (int i = 0; i < n; i++)
        {
            String[] strs = Console.ReadLine().Split(' ');
            l = int.Parse(strs[0]);
            r = int.Parse(strs[1]);
            ans += r - l + 1;
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
n = int(input())
if n == 1:
  print(1)
elif n <= 3:
  print(2)
elif n <= 7:
  print(4)
elif n <= 15:
  print(8)
elif n <= 31:
  print(16)
elif n <= 63:
  print(32)
else:
  print(64)

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

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

int main() {
    fast_io;
    
    vector<int> arr;

    string s;
    cin>>s;

    for(int i=0;i<s.length();i++) {
        arr.push_back(int(s[i]-'0'));
    }

    int total=0;
    for(int i=0;i<s.length();i++) {
        total+=arr[i];
    }

    if(total%9==0) {
        cout<<"Yes"<<endl;
    }
    else {
        cout<<"No"<<endl;
    }

}




Measured memory_bytes: 4452
#include "bits/stdc++.h"
using namespace std;
#define debug(var) cout << #var << ": " << var << endl;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
using ll = long long;
using ull = unsigned long long;
using vvint = vector<vector<int>>;
constexpr ll mod = 1e9 + 7;

int main() {

  int N; cin >> N;
  string S; cin >> S;
  int K; cin >> K;
  char c = S[K - 1];
  rep(i, N) {
	if (S[i] != c)cout << "*";
	else cout << c;
  }

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)
#define S(type,x) fscanf(stdin,"%"#type,&x)
long long n, k,s=0,
		w[100000];
long long f(long long a);
int main() {	
	S(lld, n), S(lld, k);
	int i;
	for (i = 0; i < n; i++) scanf("%lld", w + i), s += w[i];
	long long a = s / k;
	while (f(a) != n)a++;
	P(lld, a);
	return 0;
}

long long f(long long a){
	int x = 0;
	int i;
	for (i = 0; i < k; i++) {
		long long s = 0;
		while (s + w[x] <= a) {
			s += w[x++];
			if (x >= n)return n;
		}
	}
	return x;
}


Measured memory_bytes: 2568
N = int(input())
A = tuple(map(int, input().split()))
dp = [[0] * (N + 1) for _ in range(N + 1)]

for length in range(1, N + 1):
    for l in range(N - length + 1):
        r = length + l
        if (N - length) % 2:
            dp[l][r] = min(dp[l + 1][r] - A[l], dp[l][r - 1] - A[r - 1])
        else:
            dp[l][r] = max(dp[l + 1][r] + A[l], dp[l][r - 1] + A[r - 1])
print(dp[0][N])


Measured memory_bytes: 115292
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,count=0;;
  cin>>n;
  char s[n];
  for(int i=0;i<n;i++)
  {
    cin>>s[i];
    if(i>0);
    {
       if(s[i]!=s[i-1])
         count++;
    }
  }
  cout<<count;
  return 0;
}

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

using namespace std;

const int MAXN = 2E5;
int h[MAXN];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    sort(h, h + n);
    long long ans = 0;
    for (int i = 0; i < n - k; i++)
        ans += h[i];
    cout << ans << endl;
    return 0;
}


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

int main() 
{
    int n;
    cin >> n;
    int S[n];
    rep(i,n) {
        int w;
        cin >> w;
        if (i ==0) S[i] = w;
        else (S[i]) = S[i-1] + w;
    }

    int ans = 1<<30;    
    rep(i,n) {
        ans = min(ans, abs(S[n-1]-2*S[i]));
    }

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


Measured memory_bytes: 256
import numpy as np

A=int(input())
B=int(input())
C=int(input())
X=int(input())


cnt=0
for i in np.arange(A+1)*500:
    for h in np.arange(B+1)*100:
        for t in np.arange(C+1)*50:
            if i+t+h==X:
                cnt+=1
                
print(cnt)

Measured memory_bytes: 12504
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF (1 << 30 - 1)
#define LLINF (1LL << 60)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> A >> B >> N;
    if (N >= B) {
        cout << (A * (B - 1)) / B << endl;
    } else {
        cout << (A * N) / B << endl;
    }
}

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


#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::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 trace(...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){


}

void solve(){


}
int ans[200009][2];
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	string s;cin>>s;
	int n =sz(s);
	ans[0][0]=ans[0][1]=ans[1][1]=0;
	ans[1][0] = 1;
	repA(i,2,n){
		if(s[i-1]==s[i-2]){
			ans[i][0] = ans[i-1][1]+1;
		}
		else ans[i][0] = max(ans[i-1][1],ans[i-1][0])+1;
		ans[i][1] = ans[i-2][0]+1;
		if(i>=4&&s[i-1]==s[i-3]&&s[i-2]==s[i-4]) continue;
		ans[i][1] = max(ans[i][1],ans[i-2][1]+1);
	}
	cout<<max(ans[n][0],ans[n][1]);	
	return 0;
}



Measured memory_bytes: 2196
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
long long x[200002],d[200002],c[200002];
 
int lis(int n){
	int i,j,I;
/*
	for(i=-1;I=0,++i<n;d[i]=I+1)
		for(j=i-1;~j;j--)
			if(x[j]<x[i]&&I<d[j])I=d[j];
*/
	// http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn
	int sz = 1;
	c[1] = x[0];
	d[0] = 1;
	for(i=0;++i<n;){
		if(x[i] < c[1]){
			c[1] = x[i];
			d[i] = 1;
		}else if(x[i] > c[sz]){
			c[sz+1] = x[i];
			d[i] = sz+1;
			sz++;
		}else{
			int k = lower_bound(c,c+sz,x[i])-c;
			c[k] = x[i];
			d[i] = k;
		}
	}
	for(i=j=0;i<n;i++)
		if(d[i]>d[j])j=i;
	return d[j];
}
 
int main(){
	long long x1,y1,x2,y2;
	int n,xf=1,yf=1;
	scanf("%lld%lld%lld%lld%d",&x1,&y1,&x2,&y2,&n);
	if(x1>x2)swap(x1,x2),xf=-1;
	if(y1>y2)swap(y1,y2),yf=-1;
	vector<pair<long long,long long>>v;
	for(int i=0;i<n;i++){
		long long x,y;
		scanf("%lld%lld",&x,&y);
		if(x1<=x&&x<=x2 && y1<=y&&y<=y2)v.emplace_back(x*xf,y*yf);
	}
	sort(v.begin(),v.end());
	n=0;
	for(auto &e:v)x[n++]=e.second;
	n=n?lis(n):0;
	printf("%.15f\n",100.0*(x2-x1+y2-y1)-20*n+5*(n+(n>=min(x2-x1,y2-y1)+1))*M_PI);
}

Measured memory_bytes: 9068
package main

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

func main() {
	sc.Split(bufio.ScanWords)

	var n int
	fmt.Scan(&n)
	a := scanInts(n)
	b := scanInts(n)
	c := scanInts(n)
	sort.Ints(a)
	sort.Ints(c)

	ans := 0
	for i := 0; i < n; i++ {
		// j := sort.SearchInts(a, b[i])
		// k := sort.SearchInts(c, b[i]+1)
		j := lowerBound(a, b[i])
		k := upperBound(c, b[i])
		ans += j * (n - k)
	}
	fmt.Println(ans)
}

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

func lowerBound(a []int, x int) int {
	lb, ub := -1, len(a)
	for ub-lb > 1 {
		mid := (lb + ub) / 2
		if a[mid] < x {
			lb = mid
		} else {
			ub = mid
		}
	}
	return ub
}

func upperBound(a []int, x int) int {
	lb, ub := -1, len(a)
	for ub-lb > 1 {
		mid := (lb + ub) / 2
		if a[mid] <= x {
			lb = mid
		} else {
			ub = mid
		}
	}
	return ub
}

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 5760
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int S=scanner.nextInt();
		int h=S/3600;
		int amari=S-h*3600;
		int m=amari/60;
		int s=amari%60;
		System.out.println(h+":"+m+":"+s);

	}

}



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

int n,m,k,a,b,banyak[3005],hasil = 0,temp,pos,satu;
vector<int> pulau[3005];

int main() {
	memset(banyak, 0, sizeof banyak);
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		pulau[a].push_back(b);
		pulau[b].push_back(a);
		banyak[a]++;
		banyak[b]++;
	}
	while (true) {
		temp = pos = satu = 0;
		for (int i = 1; i <= n; i++) {
			if (banyak[i] > temp) {
				temp = banyak[i];
				pos = i;
			}
			if (banyak[i] == 1)
				satu = i;
		}
		if (temp == 0)
			break;
		hasil++;
		if (satu != 0) {
			for (int i = 0; i < pulau[satu].size(); i++)
				if (banyak[pulau[satu][i]] > 0) {
					pos = pulau[satu][i];
					break;
				}
		}
		for (int i = 0; i < pulau[pos].size(); i++)
			if (banyak[pulau[pos][i]] > 0)
				banyak[pulau[pos][i]]--;
		banyak[pos] = 0;
	}
	if (hasil <= k)
		printf("%d\n", hasil);
	else
		printf("Impossible\n");
	return 0;
}

Measured memory_bytes: 1672
def main():
    n = int(input())
    s = list(input())

    s_b = [1 if c=='#' else 0 for c in s]
    s_w = [1 if c=='.' else 0 for c in s[::-1]]

    s_b = cumsum(s_b)
    s_w = cumsum(s_w)[::-1]

    ans = []
    for i in range(n):
        ans.append(s_b[i]+s_w[i+1])

    print(min(ans))

def cumsum(a):
    s = 0
    sums = [0]
    for a_i in a:
        s+=a_i
        sums.append(s)

    return sums


if __name__ == "__main__":
    main()

Measured memory_bytes: 28368
#include<stdio.h>

double factorial(double n);

int main(void)
{
  double n;
  scanf("%lf",&n);
  printf("%.f\n",factorial(n));
  return 0;
}

double factorial(double n)
{
  if(n>0)
    return n*factorial(n-1);
  else
    return 1;
}

Measured memory_bytes: 0
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <complex>

#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;


ll powMod(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll t = powMod(x, n/2, mod);
  t = t * t % mod;
  if (n & 1) return t * x % mod;
  return t;
}

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

int main(void) {

  long double r;
  cin >> r;

  cout << 2.0 * r * 3.14159265 << endl;
}


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

using namespace std;

int main()
{
   string s;
   cin >> s;
   if("Sunny" == s)
     cout << "Cloudy";
   else if("Cloudy" == s)
     cout << "Rainy";
   else if("Rainy" == s)
     cout << "Sunny";
   return 0;
}

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

int dp[100002];

int n,m;
vector<vector<int> > v;
vector<bool> vis;
int dfs(int node)
{
    vis[node] = true;
    if(v[node].size() == 0)
        return 0;
    if(dp[node] != -1)
        return dp[node];
    for(int i=0;i < v[node].size();i++)
    {
        dp[node] = max(dp[node],1+dfs(v[node][i]));
    }
    return dp[node];
}
int main()
{
    cin>>n>>m;
    vis.resize(n+1,false);
    v.resize(n+1);
    memset(dp,-1,sizeof(dp));
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
            dfs(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans = max(ans,dp[i]);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 7424
import math
N=int(input())
lst=[int(s) for s in input().split()]
lst2=[int(s) for s in input().split()]
def ind(ls):
  cha=[i+1 for i in range(N)]
  ans=1
  for i in range(N):
    x=cha.index(ls[i])
  #  print(x)
    ans+=(x)*math.factorial(N-1-i)
   # print(ans)
    cha.remove(ls[i])
  return ans
a=ind(lst)
b=ind(lst2)
print(abs(a-b))
    

Measured memory_bytes: 3064
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <bitset>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int bitcount(int x){
  int ret = 0;
  while(x){
    ret += x&1;
    x >>= 1;
  }
  return ret;
}

struct Edge{
  int to, cost;
  Edge(int a, int b){
    to = a;
    cost = b;
  }
};

int N, M, L, S, T;
//vector<Edge>G[305];
int dp[1<<16][16];
int G[300][300];
int jiro[16];
int eat[16];

int main()
{
  while(1){
    cin >> N >> M >> L >> S >> T; 
    if(N == 0 && M == 0 && L == 0 && S == 0 && T == 0) break;
    S--;
  rep(i, N) rep(j, N) G[i][j] = INF;
  rep(i, N) G[i][i] = 0;
  for(int i=0;i<M;i++){
    int a, b, c; cin >> a >> b >> c; a--; b--;
    //    G[a].push_back(Edge(b, c));
    //    G[b].push_back(Edge(a, c));
    G[a][b] = G[b][a] = c;
  }

  rep(i, L){
    cin >> jiro[i] >> eat[i]; jiro[i]--;
  }

  rep(k, N) G[k][k] = 0;
  rep(k, N) rep(i, N) rep(j, N){
    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
  }

  for(int i=0;i<1<<16;i++) for(int j=0;j<16;j++) dp[i][j] = INF;
  for(int i=0;i<L;i++) dp[1<<i][i] = G[S][jiro[i]] + eat[i];
  for(int i=0;i<1<<L;i++){
    for(int j=0;j<L;j++){
      for(int k=0;k<L;k++){
	dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j] + G[jiro[j]][jiro[k]] + eat[k]);
	//	if(dp[i|(1<<k)][k] != INF){
	//	  cout << bitset<16>(i|(1<<k)) << " " << k << " " << dp[i|(1<<k)][k] << endl;
	  //	}
      }
    }
  }
  int ret = 0;
  for(int i=0;i<1<<L;i++){
    for(int j=0;j<L;j++){
      if(dp[i][j] + G[jiro[j]][S] <= T){
	//	cout << bitset<16>(i) << " " << j << " " << " " << jiro[j] << " " << S <<" " << dp[i][j] << " " <<  G[jiro[j]][S] << endl;      
	ret = max(ret, bitcount(i));
      }
    }
  }

  cout << ret << endl;
  }
  return 0;
}

Measured memory_bytes: 7456
"""
int(input())
map(int, input().split())
list(map(int, input().split()))
input()
input().split()
"""


n = int(input())
mod = 1000000007

tmp = 1
diff = 1
eight = 1

for i in range(n):
    tmp *= 10
    tmp %= mod
    diff *= 9
    diff %= mod
    eight *= 8
    eight %= mod

ans = tmp - 2*diff + eight
ans %= mod
print(ans)

# tmp = (10**n)%mod
# diff = 2*(9**n)%mod
# eight = (8**n)%mod

# ans = tmp - diff + eight
# print(ans)

Measured memory_bytes: 9188
#include<stdio.h>
#include<iostream>
using namespace std;

int N,T;
int main (){
    cin >> N >> T;
    int time = T;
    int total = T;
    for(int i=0; i<N; i++){
        int t;
        cin >> t;
        if ( t >= time){
            total += T;
            time = t + T;
        } else {
            total += T - (time - t) ;
            time = t + T;
        }
    }
    cout << total << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stdio.h>
#define ll long long
#define maxn 1001
using namespace std;
ll k,n;
ll arr[maxn];
ll ans;
int main()
{
	cin>>k>>n;
	for(int i=0;i<k;i++)
	{
		cin>>arr[i];
	}
	sort(arr,arr+k);
	for(int i=0;i<n;i++)
	{
		ans+=arr[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;

public class Main{
        public static void main(String[]args){

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] V = new int [N];
        int[] C = new int [N];
        int[] P = new int [N];
        int t = 0;

        for(int i=0;i<N;i++){
            V[i] = sc.nextInt();
        }
        
        for(int i=0;i<N;i++){
            C[i] = sc.nextInt();
        }
        
        for(int i=0;i<N;i++){
            P[i] = V[i]-C[i];
        
            if(P[i]>0) {
            	t+=P[i];
            }
        }

        System.out.print(t);
        sc.close();
    }
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
    ll n,m,x,y;cin >>n>>m>>x>>y;
    vector<ll>a(n);
    vector<ll>b(m);
    ll mint=INF,mx=-INF;
    for (int i = 0; i < n; ++i) {
        cin >>a[i];
        mx=max(a[i],mx);
    }
    for (int i = 0; i < m; ++i) {
        cin >>b[i];
        mint=min(mint,b[i]);
    }
    bool flg=false;
//    cout <<mint<<" "<<mx<<endl;
    for (ll z = x+1; z <=y; ++z) {
        if(z<=mint&&z>mx)flg=true;
    }
    if(!flg)puts("War");
    if(flg)puts("No War");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define LLI long long int
#define fst first
#define snd second
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
#ifndef M_E
#define M_E 2.71828182845904523536
#endif
#ifdef DEBUG
#include <boost/core/demangle.hpp>
#define dump(x) cerr << "L" << __LINE__ << ": in " << __PRETTY_FUNCTION__ << " \e[32;1m" << boost::core::demangle(typeid(x).name()) << "\e[37m" << " " << (#x) << " = " << (x) << "\e[m" << endl;
#else
#define dump(x)
#endif
#define pln(x) cout << (x) << endl
using namespace std;
template <typename T> using V = vector<T>;
template <typename T, typename U> using P = pair<T,U>;
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename Iter> ostream& out_container(ostream &os, Iter first, Iter last){
  os << "{"; auto itr = first; while(itr != last){if(itr != first) os << ","; os << *itr; ++itr;} os << "}"; return os;
}

template <typename T> ostream& operator<<(ostream &os, const vector<T> &c){return out_container(os,ALL(c));}
template <typename T> ostream& operator<<(ostream &os, const deque<T> &c){return out_container(os,ALL(c));}
template <typename T> ostream& operator<<(ostream &os, const set<T> &c){return out_container(os,ALL(c));}
template <typename T> ostream& operator<<(ostream &os, const unordered_set<T> &c){return out_container(os,ALL(c));}
template <typename T, typename U> ostream& operator<<(ostream &os, const map<T,U> &c){return out_container(os,ALL(c));}
template <typename T, typename U> ostream& operator<<(ostream &os, const unordered_map<T,U> &c){return out_container(os,ALL(c));}
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T,U> &p){os << "(" << p.first << "," << p.second << ")"; return os;}

template <typename T> T& chmin(T &a, const T &b){return a = min(a,b);}
template <typename T> T& chmax(T &a, const T &b){return a = max(a,b);}

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

  int N;
  while(cin >> N){
    vector<int> h(N); cin >> h;

    int ans = 0;


    REP(i,N){
      while(h[i] != 0){
	FOR(j,i,N){
	  if(h[j] == 0) break;
	  --h[j];
	}
	++ans;
      }
    }
    
    pln(ans);
  }
  
  return 0;
}


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

using namespace std;

using ll = long long;
const ll MOD = 1000000007; //10^9+7

ll modpow(ll a, ll n) {
    if (n == 1) return a % MOD;

    if (n % 2 == 0) {
        ll t = modpow(a, n / 2);
        return (t * t) % MOD;
    }
    else {
        return (a * modpow(a, n - 1)) % MOD;
    }
}

ll comb(ll n, ll a) {
    ll ans = 1;
    for (int i = 0; i < a; i++) {
        ans = (ans * (n - i)) % MOD;
    }

    for (int i = 1; i <= a; i++) {
        ans = (ans * modpow(i, MOD - 2)) % MOD;
    }
    return ans;
}

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

    cout << (MOD + MOD + modpow(2, n) - comb(n, a) - comb(n, b) - 1) % MOD<< endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

const int64 mod = 998244353;

int main()
{
	int64 nn, kk;
	cin >> nn >> kk;
	vector<pair<int64, int64>> memo(kk);
	for(int64 ii = 0;ii < kk;ii++)
	{
		cin >> memo[ii].first >> memo[ii].second;
	}
	vector<int64> vv(3 * nn, 0), table(3 * nn, 0);
	vv[0] = 1;
	for(auto ite = memo.begin();ite != memo.end();ite++)
	{
		vv[(*ite).first] += vv[0];
		if((*ite).second + 1 < nn)
		{
			vv[(*ite).second + 1] -= vv[0];
		}
	}
	
	for(int64 ii = 1;ii < nn;ii++)
	{
		vv[ii] += table[ii - 1];
		while(vv[ii] < 0)
		{
			vv[ii] += mod;
		}
		vv[ii] %= mod;
		table[ii] = vv[ii];
		for(auto ite = memo.begin();ite != memo.end();ite++)
		{
			if(ii + (*ite).first < nn)
			{
				vv[ii + (*ite).first] += table[ii];
				vv[ii + (*ite).first] %= mod;
			}
			if(ii + (*ite).second + 1 < nn)
			{
				vv[ii + (*ite).second + 1] -= table[ii];
				while(vv[ii + (*ite).second + 1] < 0)
				{
					vv[ii + (*ite).second + 1] += mod;
				}
				vv[ii + (*ite).second + 1] %= mod;
			}
		}
	}
	
	cout << table[nn - 1] << endl;
	return 0;
}

Measured memory_bytes: 12760
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue> 
using namespace std;
int a,b,c,x,f;
int main() 
{
 cin>>a>>b>>c>>x;
 for (int i=0;i<=a;i++){
 for (int m=0;m<=b;m++){
 for (int n=0;n<=c;n++){
 if (i*500+m*100+n*50==x)
 f++;
 }}}
 cout<<f;
 system("pause");
 return 0;
}        

Measured memory_bytes: 504
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
  int W, a, b, ans;

  cin >> W >> a >> b;

  if(a+W < b){
    ans = b - (a+W);
  }else if(b+W < a){
    ans = a - (b+W);
  }else{
    ans = 0;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program {
    static void Main (string[] args) {
        int N = int.Parse (Console.ReadLine ());
        var str = Console.ReadLine ().Split (' ');
        var ary = str.Select (x => int.Parse (x)).ToArray ();

        int Max = int.Parse (str[0]);
        int ans = 1;

        for (var i = 1; i < N; i++) {
            if (Max <= ary[i]) {
                Max = ary[i];
                ans++;
            }
        }
        Console.WriteLine (ans);
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100000000000
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;
 
int main(){
    int d; cin >> d;
    vector<int> c(26);
    rep(i,26) cin >> c[i];
    vector<vector<int> > s(d);
    rep(i,d)rep(j,26){
        int a; cin >> a;
        s[i].push_back(a);
    }
 
    //vector<int> ld(26,0);
    vector<vector<int> > ds(26);
    vector<int> days(d,1);

    
    //ll ans=0;
    rep(i,d){
        int t=days[i];
        ds[t].push_back(i);
        /*
        ld[t]=i+1;
        ans+=s[i][t];
        rep(j,26){
            ans-=c[j]*(i+1-ld[j]);
        }
        */
    }
 
    rep(i,1000){
        rep(Q,26)rep(D,d){
        int pd=days[D];
        int be,af,be2,af2;
        int r,l;
        l=-1;
        r=ds[pd].size();
        while(l+1<r){
            int c=(l+r)/2;
            if(ds[pd][c]<=D) l=c;
            else r=c;
        }
        if(r==ds[pd].size()) af=d;
        else af=ds[pd][r];
        l=-1;
        r=ds[pd].size();
        while(l+1<r){
            int c=(l+r)/2;
            if(ds[pd][c]>=D) r=c;
            else l=c;
        }
        if(l==-1) be=-1;
        else be=ds[pd][l];

        int l2=-1;
        r=ds[Q].size();
        while(l2+1<r){
            int c=(l2+r)/2;
            if(ds[Q][c]<=D) l2=c;
            else r=c;
        }
        if(r==ds[Q].size()) af2=d;
        else af2=ds[Q][r];
        l2=-1;
        r=ds[Q].size();
        while(l2+1<r){
            int c=(l2+r)/2;
            if(ds[Q][c]>=D) r=c;
            else l2=c;
        }
        if(l2==-1) be2=-1;
        else be2=ds[Q][l2];

        if(c[Q]*(D-be2)*(af2-D)+s[D][Q]-c[pd]*(D-be)*(af-D)-s[D][pd]>0){
            days[D]=Q;
            ds[pd].erase(ds[pd].begin()+l+1);
            ds[Q].insert(ds[Q].begin()+l2+1,D);
        }
    }
    }
    rep(i,d) cout << days[i]+1 << endl;
return 0;
}

Measured memory_bytes: 3728
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define all(X) X.begin(),X.end()

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   str.substr (x) : returns a substring str[x],... end of string
   str.find(qtr) : returns the first occurenece of qtr in str */

const int M = (1<<20)+5;
const int md = 1e9+7;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll cm[M],m[M];

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

	ll i,j,k,l,n,ans = 0;

	k = 3;
	cin >> n;

	for(i=1;i<=n;++i)
		m[i] = 1;
	for(i=2;i<=n;++i)
	{
		if(cm[i])
		{
			if(m[i] == 0)
				continue;
			if(cm[i]%2)
				m[i] = -1;
			else
				m[i] = 1;
			continue;
		}
		m[i] = -1;
		for(j=i+i;j<=n;j+=i)
		{
			cm[j]++;
			if(j%(i*i) == 0)
				m[j] = 0;
		}
	}

	for(j=1;j<=n;++j)
	{
		l = n/j;
		ll c = 0;
		for(i=1;i<=l;++i)
		{
			c = (c + 1ll*m[i]*pwr(n/(i*j),k,md))%md;
		}
		ans = (ans + 1ll*j*c%md)%md;
	}

	cout << ans << "\n";
}


	

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i,n)cin >> a[i];
  sort(a.begin(),a.end());
  ll ub = 2e18;
  ll lb = -2e18;
  while(ub-lb>1){
    ll mid = (ub+lb)/2;
    ll cnt = 0;
    //    cout << "mid " << mid << endl;
    rep(i,n-1){
      if(a[i]>0){
	if(a[n-1]*a[i]<=mid) cnt += (n-1)-(i+1)+1;
	else if(a[i+1]*a[i]>mid) continue;
	else{
	  ll ub2 = n-1;
	  ll lb2 = i+1;
	  while(ub2-lb2>1){
	    ll mid2 = (ub2+lb2)/2;
	    if(a[i]*a[mid2]<=mid) lb2=mid2;
	    else ub2=mid2;
	  }
	  cnt += ub2 - (i+1);	  
	}
      }
      else{
	if(a[i+1]*a[i]<=mid) cnt += (n-1)-(i+1)+1;
        else if(a[n-1]*a[i]>mid) continue;
        else{
	  ll ub2 = n-1;
          ll lb2 = i+1;
          while(ub2-lb2>1){
            ll mid2 = (ub2+lb2)/2;
            if(a[i]*a[mid2]>mid) lb2=mid2;
            else ub2=mid2;
          }
          cnt += (n-1) - lb2;
	}
      }
    }
    //    cout << "mid cnt " << mid << " " << cnt << endl;
    if(cnt<k) lb=mid;
    else ub = mid;
  }
  cout << ub << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define all( X ) ( X ).begin(), ( X ).end()

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
template <class T> void cumulative_sum( T array, size_t N );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;

template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	bool is_visited = false;
} node;
typedef struct {
	int to;
	int cost;
	P <int, int> change;
} edge;

int main(){
	int N; cin >> N;
	vector<ll> f(N+1, 1);
	ll sum = 1;
	rep(i,2,N+1){
		int cnt = i;
		for(;cnt <=N; cnt+=i){
			f[cnt]++;
		}
		sum+=i*f[i];
		// printf("(%d, %d)", i, f[i]);
		// cout << i << ":";
		// for(auto a:f){
		// 	cout << a << " ";
		// }
		// cout << endl;
	}
	cout << sum << endl;
}

int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
template <class T> void cumulative_sum( T array, size_t N ) {
	rep( i, 1, N + 1 ){
		array[ i ] += array[ i - 1 ];
	}
}
template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}


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

using ll = long long;
const ll INF = 1e18;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) {
        cin >> a[i];
        a[i]--;
    }
    int ans = 0;
    rep(i, N) {
        if (a[a[i]] == i) ans++;
    }
    cout << ans / 2 << "\n";
}

Measured memory_bytes: 640
import math
import sys

input = sys.stdin.readline

N = int(input())
trains = [[int(x) for x in input().split()] for _ in range(N - 1)]

for i in range(N):
    t = 0
    for j in range(i, N - 1):
        C, S, F = trains[j]
        if t <= S:
            t = S
        else:
            x = math.ceil((t - S) / F)
            t = S + F * x
        t += C
    print(t)


Measured memory_bytes: 3188
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long K = sc.nextLong();
    int[] A = new int[N];
    for (int i = 0; i < N; i++)
      A[i] = sc.nextInt();
    sc.close();

    int[] n = new int[N];
    Arrays.fill(n,  -1);

    int cnt = 1;
    n[0] = cnt;
    int next = A[0] - 1;
    while (n[next] < 0) {
      n[next] = ++cnt;
      next = A[next] - 1;
    }

    int begin = n[next] - 1;
    int loop = cnt - begin;
    long mod = (K < begin) ? (K - begin) : ((K - begin) % loop);

    int ans = 1;
    for (int i = 0; i < begin + mod; i++)
      ans = A[ans - 1];
    System.out.println(ans);
  }
}


Measured memory_bytes: 60524
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    r = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][k] + A[k][j] < A[i][j]:
                    return -1
                if A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                r += A[i][j]
    return r

print(main())


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


void solve(long long X, long long Y, long long Z){
    cout << Z << " " <<  X << " " <<  Y <<  endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    long long Z;
    scanf("%lld",&Z);
    solve(X, Y, Z);
    return 0;
}


Measured memory_bytes: 384
N, Q = gets.split.map &:to_i
$nodes = *0...N
def root(a)
  while $nodes[a] != a do
    $nodes[a] = $nodes[$nodes[a]]
    a = $nodes[a]
  end
  a
  # a == $nodes[a] ? a : $nodes[a] = root($nodes[a])
end
def unite(a, b)
  $nodes[root(a)] = b
end
def same?(a, b)
  $nodes[root(a)] == $nodes[root(b)]
end

$<.map{|s|
  com, x, y = s.split.map &:to_i
  if com == 0
    unite(x, y)
  else
    p same?(x, y) ? 1 : 0
  end
}

Measured memory_bytes: 9992
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;
const ll MOD = 7+(1e+9);

int main (){
  string s;
  cin>>s;
  ll ans=0;
  ll n=s.size();
  for(ll i=0;i<n;i++){
    ll j=0;
    for(j=i;j<n;j++){
      if(s[j]!='A'&&s[j]!='C'&&s[j]!='G'&&s[j]!='T'){
        break;
      }
    }
    if(ans<(j-i)){
      ans=(j-i);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256