akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
int N,insu[101],a,b,c,d,e;
int main()
{
	cin >> N;
	
	for(int i=2; i<=N; i++)
	{
		int Num=i;
		for(int j=2; j<=N; j++)
		{
			while(Num%j==0)
			insu[j]++,Num/=j;
			
			if(Num==1)
			break;
		}
	}
	
	for(int i=2; i<=N; i++)
	{
		if(insu[i]>=2)
		a++;
		if(insu[i]>=4)
		b++;
		if(insu[i]>=14)
		c++;
		if(insu[i]>=24)
		d++;
		if(insu[i]>=74)
		e++;
	}
	
	cout << b*(b-1)/2*(a-2)+d*(a-1)+(b-1)*c+e;
}

Measured memory_bytes: 256
X, N = list(map(int,input().split()))
if N !=0:
  P = list(map(int,input().split()))
  ab = 100
  for i in range(-100,200):
    if i not in P:
      if abs(X-i)<ab:
        ab = abs(X-i)
        ans = i
  print(ans)
else:
  print(X)

Measured memory_bytes: 9192
n = int(input())
ans_dict = {}
ans = 0
for i in range(n):
    s = "".join(sorted(input()))
    if s in ans_dict:
        ans_dict[s] += 1
    else:
        ans_dict[s] = 1
for j in ans_dict.values():
    ans += j * (j - 1) // 2
print(ans)

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

using namespace std;

typedef long long ll;

signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto& x : a){
        cin >> x;
    }
    vector<int> rui(n, a[0]);
    for(int i = 1; i < n; ++i)
        rui[i] = rui[i - 1] + a[i];
    int ans = 1e9;
    for(int i = 0; i < n; ++i){
        int c = i + 1;
        int bound = rui[i] / c;
        ans = min(bound, ans);
    }
    cout << ans << endl;
}




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

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

bool isprime(ll n){
    if (n < 2) return false;
    else if (n == 2) return true;
    else if (n % 2 == 0) return false;

    double s = sqrt(n);
    for (ll i = 3; i <= s; i += 2){
        if (n % i == 0){
            return false;
        }
    }

    return true;
}

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

    vector<ll> n_gcd, m_gcd;
    for(ll i = 1; i * i <= n; i++){
        if(n % i == 0){
            n_gcd.push_back(i);
            n_gcd.push_back(n / i);
        }
    }

    for(ll i = 1; i * i <= m; i++){
        if(m % i == 0){
            m_gcd.push_back(i);
            m_gcd.push_back(m / i);
        }
    }

    vector<ll> ans;
    for(int i = 0; i < n_gcd.size(); i++){
        auto itr = find(m_gcd.begin(), m_gcd.end(), n_gcd[i]);
        if(itr != m_gcd.end()){
            ans.push_back(n_gcd[i]);
        }
    }

    ll cou = 0;
    for(int i = 0; i < ans.size(); i++){
        if(isprime(ans[i])){
            cou++;
        }
    }

    cout << cou + 1 << endl;
}

Measured memory_bytes: 512
#include <stdio.h>
int main(void){
    int x,y;
    scanf("%d%d",&x,&y);
    if(x==2||y==2) printf("No\n");
    else if((x<8&&x%2==1)&&((y<8&&y%2==1)||(y>7&&y%2==0))) printf("Yes\n");
    else if(x>7&&x%2==0&&y%2==0) printf("Yes\n");
    else if((x<7&&x%2==0)&&((y<7&&y%2==0)||(y>8&&y%2==1))) printf("Yes\n");
    else if(x==9&&y==11) printf("Yes\n");
    else printf("No\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
vector <int> g[N];
ll vis[N];
void dfs(ll v,ll p){
    for (auto u : g[v]){
        if (u==p) continue;
        dfs(u,v);
        if (vis[u]==0 && vis[v]==0){
            vis[u]=1;
            vis[v]=1;
        }
    }
}
int32_t main(){
    sync;
    ll n;
    cin >> n;
    for (int i=0;i<n-1;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,1);
    for (int i=1;i<=n;i++) if (vis[i]==0) kill("First");
    kill("Second");
}

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

#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> v;
  return s;
}


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

    int r, g, b; cin >> r >> g >> b;
    cout << (((g*10+b)%4)?"NO":"YES") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int N;
  cin >> N;
  vector<int> a;
  rep(i, N) {
    int ai;
    cin >> ai;
    a.pb(ai);
  }
  sort(all(a));

  int max = a[N-1];

  long double center = (long double)max / 2;
  long double lengthFromCenter = INF;
  int candidate = -1;

  rep(i, N - 1) {
    long double len = abs((long double)a[i] - center);
    if (len < lengthFromCenter) {
      lengthFromCenter = len;
      candidate = a[i];
    }
  }
  cout << max << " " << candidate << endl;
}


Measured memory_bytes: 892
#include<iostream>

using namespace std;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 1e5 + 5;

int32_t main()
{
	IOS;
	int n, a, b;
	cin >> n >> a >> b;
	int cycle = a + b;
	int tot = n / (a + b);
	int ans = tot * a;
	n %= (a + b);
	ans += min(n, a);
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int Max_N(131072 + 5);
typedef long long int LL;

void Get_Val(int &Ret)
{
	Ret = 0;
	char ch;
	while (ch = getchar(), ch > '9' || ch < '0')
		;
	do
	{
		(Ret *= 10) += ch - '0';
	}
	while (ch = getchar(), ch >= '0' && ch <= '9');
}

int N, Weight[Max_N];
vector<int> Son[Max_N];

void init()
{
	Get_Val(N);
	for (int i = 2, fa;i <= N;++i)
		Get_Val(fa), Get_Val(Weight[i]), Son[fa].push_back(i);
}

struct node
{
	node(const LL &_a = 0LL, const LL &_b = 0LL) : a(_a), b(_b) {}
	LL a, b;
};
LL D;
vector<node> Ans[Max_N], Tmp;

inline bool comp(const node &v1, const node &v2)
{
	return v1.a == v2.a ? v1.b < v2.b : v1.a < v2.a;
}

void dfs(const int &u)
{
	Ans[u].clear();
	if (Son[u].size())
	{
		int a(Son[u][0]), b(Son[u][1]);
		dfs(a), dfs(b);
		Tmp.clear();
		for (int i = 0, j = 0;i < Ans[a].size();++i)
		{
			while (j + 1 < Ans[b].size() && Ans[a][i].b + Ans[b][j + 1].a <= D)
				++j;
			if (j < Ans[b].size() && Ans[a][i].b + Ans[b][j].a <= D)
				Tmp.push_back(node(Ans[a][i].a + Weight[u], Ans[b][j].b + Weight[u]));
		}
		for (int i = 0, j = 0;i < Ans[b].size();++i)
		{
			while (j + 1 < Ans[a].size() && Ans[b][i].b + Ans[a][j + 1].a <= D)
				++j;
			if (j < Ans[a].size() && Ans[b][i].b + Ans[a][j].a <= D)
				Tmp.push_back(node(Ans[b][i].a + Weight[u], Ans[a][j].b + Weight[u]));
		}
		sort(Tmp.begin(), Tmp.end(), comp);
		if (Tmp.size())
		{
			Ans[u].push_back(Tmp[0]);
			for (int i = 1;i < Tmp.size();++i)
				if (Tmp[i].b < Ans[u][Ans[u].size() - 1].b)
					Ans[u].push_back(Tmp[i]);
		}
	}
	else
		Ans[u].push_back(node(Weight[u], Weight[u]));
}

bool check(const LL &d)
{
	D = d;
	dfs(1);
	return Ans[1].size() != 0;
}

void work()
{
	LL l(0LL), r(1LL), mid;
	for (int s = 1;s <= N;++s)
		r += Weight[s];
	while (l < r)
	{
		mid = l + ((r - l) >> 1LL);
		if (check(mid))
			r = mid;
		else
			l = mid + 1LL;
	}
	printf("%lld", l);
}

int main()
{
	init();
	work();
	return 0;
}

Measured memory_bytes: 32372
#include <iostream>
#include <vector>
#include <string>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;

int main(){
    string w;
    cin >> w;
    vector<int>dic(26);
    rep(i, w.size()){
        dic[w[i]-'a']++;
    }
    bool flag = true;
    rep(i, dic.size()){
        if(dic[i]%2)    flag = false;
    }
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import sys
n, a, b, c = map(int, input().split())

if a+b+c == 0:
  print("No")
  sys.exit()
elif a+b+c == 1:
  ans = [None]*n
  for i in range(n):
    s = input()
    if (s == "AB" and c == 1) or (s == "AC" and b == 1) or (s == "BC" and a == 1):
      print("No")
      sys.exit()
    if s == "AB":
      if a == 1:
        ans[i] = "B"
        a, b = 0, 1
      else:
        ans[i] = "A"
        a, b = 1, 0
    if s == "BC":
      if b == 1:
        ans[i] = "C"
        b, c = 0, 1
      else:
        ans[i] = "B"
        b, c = 1, 0
    if s == "AC":
      if c == 1:
        ans[i] = "A"
        c, a = 0, 1
      else:
        ans[i] = "C"
        c, a = 1, 0
  print("Yes")
  for i in range(n):
    print(ans[i])

else:
  ans = [None]*n
  s = [input() for _ in range(n)]
  for i in range(n):
    if (s[i] == "AB" and a == 0 and b == 0) or (s[i] == "AC" and c == 0 and a == 0) or (s[i] == "BC" and b == c == 0):
      print("No")
      sys.exit()
    if s[i] == "AB":
      if a == 0:
        ans[i] = "A"
        a += 1
        b -= 1
      elif b == 0:
        ans[i] = "B"
        a -= 1
        b += 1
      elif i != n-1 and s[i] != s[i+1]:
        if s[i+1] == "BC":
          ans[i] = "B"
          b += 1
          a -= 1
        if s[i+1] == "AC":
          ans[i] = "A"
          b -= 1
          a += 1
      else:
        if b > a:
          ans[i] = "A"
          a += 1
          b -= 1
        else:
          ans[i] = "B"
          a -= 1
          b += 1
          
      
    if s[i] == "BC":
      if b == 0:
        ans[i] = "B"
        b += 1
        c -= 1
      elif c == 0:
        ans[i] = "C"
        b -= 1
        c += 1
      elif i != n-1 and s[i] != s[i+1]:
        if s[i+1] == "AC":
          ans[i] = "C"
          c += 1
          b -= 1
        if s[i+1] == "AB":
          ans[i] = "B"
          c -= 1
          b += 1
      else:
        if b < c:
          ans[i] = "B"
          b += 1
          c -= 1
        else:
          ans[i] = "C"
          b -= 1
          c += 1
      
    if s[i] == "AC":
      if c == 0:
        ans[i] = "C"
        c += 1
        a -= 1
      elif a == 0:
        ans[i] = "A"
        c -= 1
        a += 1
      elif i != n-1 and s[i] != s[i+1]:
        if s[i+1] == "AB":
          ans[i] = "A"
          a += 1
          c -= 1
        if s[i+1] == "BC":
          ans[i] = "C"
          a -= 1
          c += 1
      else:
        if c < a:
          ans[i] = "C"
          c += 1
          a -= 1
        else:
          ans[i] = "A"
          c -= 1
          a += 1
  print("Yes")
  for i in range(n):
    print(ans[i])

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

int main() {

  int long long N,K,R,S,P,i;
  string T,Ta;
  int ans=0;
  
  cin >> N >> K >> R >> S >> P >> T;

  for ( i = 0; i < N; i++)
  {
    if (T[i]=='r')
    {
      Ta.push_back('p');
      ans+=P;
      if (i+1>=K&&Ta[i-K]=='p')
      {
        if (T[i-K]==Ta[i-K])
        {
          Ta[i-K]='s';
        }
        else
        {
          Ta[i]='r';
          ans-=P;
        }
      }
    }else if(T[i]=='s')
    {
      Ta.push_back('r');
      ans+=R;
      if (i+1>=K&&Ta[i-K]=='r')
      {
        if (T[i-K]==Ta[i-K])
        {
          Ta[i-K]='p';
        }
        else
        {
          Ta[i]='s';
          ans-=R;
        }
      }
    }else if(T[i]=='p')
    {
      Ta.push_back('s');
      ans+=S;
      if (i+1>=K&&Ta[i-K]=='s')
      {
        if (T[i-K]==Ta[i-K])
        {
          Ta[i-K]='r';
        }
        else
        {
          Ta[i]='p';
          ans-=S;
        }
      }
    }
    
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;
const int N = 510;
const int M = N*N;
int _w;

int n, m, a[M];

struct Node {
	int r, v;
	Node() {}
	Node( int r, int v ):
		r(r), v(v) {}
	bool operator<( const Node &rhs ) const {
		return r > rhs.r;
	}
};
typedef vector<Node>::iterator viter;
vector<Node> v[M];
priority_queue<Node> pq;

int main() {
	cin >> n, m = n*n;
	for( int i = 1; i <= n; ++i ) {
		int x;
		cin >> x, a[x] = i;
		for( int j = 1; j < i; ++j )
			v[1].push_back( Node(x-1, i) );
		for( int j = i+1; j <= n; ++j )
			v[x+1].push_back( Node(m, i) );
	}
	for( int i = 1; i <= m; ++i ) {
		for( viter it = v[i].begin(); it != v[i].end(); ++it )
			pq.push(*it);
		if( !a[i] ) {
			if( pq.empty() ) return puts("No"), 0;
			Node o = pq.top(); pq.pop();
			if( o.r < i ) return puts("No"), 0;
			a[i] = o.v;
		}
	}
	if( !pq.empty() ) return puts("No"), 0;
	puts("Yes");
	for( int i = 1; i <= m; ++i )
		printf( "%d ", a[i] );
	puts("");
	return 0;
}


Measured memory_bytes: 12144
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())

lis = [0]*(w-1)
n = 0
for i in range(2**(w-1)):
    
    tmp = bin(i)[2:].zfill(w-1)
    if '11' in tmp:continue
    n += 1
    for j in range(w-1):
        lis[j] += int(tmp[j])


res = [1]+[0]*(w-1)
for i in range(h):
    res2 = res.copy()
    for j in range(w):
        if j == 0:
            a=0
            x = 0
        else:
            a = lis[j-1]
            x = res[j-1]
        if j== w-1:
            b = 0
            y = 0
        else:
            b = lis[j]
            y = res[j+1]
        res2[j] = x*a + res[j]*(n - a - b) + y*b
    res = res2
print(res[k-1] % (10**9+7))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int n, m, s, g1, g2;
int d[110][110];

void init(int n){
   rep(i, 0, n){
       rep(j, 0, n){
           d[i][j] = INF;
           if(i == j) d[i][j] = 0;
       }
   }
}

void warshall_floyd(){
   rep(k, 0, n){
       rep(i, 0, n){
           rep(j, 0, n){
               d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
           }
       }
   }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(1){
        cin >> n >> m >> s >> g1 >> g2;
        if(n + m + s + g1 + g2 == 0) break;
        init(n);
        s--; g1--; g2--;
        rep(i, 0, m){
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            d[a][b] = c;
        }
        warshall_floyd();
        int MIN = INF;
        rep(i, 0, n){
            int tmp = d[s][i] + d[i][g1] + d[i][g2];
            chmin(MIN, tmp);
        }
        cout << MIN << endl;
    }
}


Measured memory_bytes: 3172
let s = read_line ()
let n = String.length s
let _ =
  for i = 0 to n - 1 do
    for j = i to n do if String.sub s 0 i ^ String.sub s j (n - j) = "keyence" then (print_endline "YES"; exit 0) done done;
  print_endline "NO"

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
  int N, T[200], M, P[200], X[200];
  long long sum;

  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> T[i];
    sum += T[i];
  }

  cin >> M;

  for (int i = 0; i < M; i++) {
    cin >> P[i] >> X[i];
    P[i]--;
  }

  for (int i = 0; i < M; i++) {
    cout << (sum + X[i] - T[P[i]]) << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i) sort((i).begin(),(i).end(), greater<int>());
#define YES(i) cout << ((i) ? "Yes" : "No") << endl;
constexpr auto INF = 1000000000;
constexpr auto LLINF = 9223372036854775807;
constexpr auto mod = 1000000007;

ll dp[101][100000];

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

int main() {

	int n, W;
	cin >> n >> W;
	VI w(n);
	vector<ll> v(n);
	FOR(i, n)cin >> w[i] >> v[i];

	FOR(i, n)eFOR(j, W) {
		if (w[i] <= j)chmax(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
		chmax(dp[i + 1][j], dp[i][j]);
	}

	cout << dp[n][W] << endl;
}

Measured memory_bytes: 78336
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << max(a * b,c * d) << endl;
}

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

int main (void){
    int p, q, r;
    cin >> p >> q >> r;
    if(p + q < r + q){
        if(p + q < p + r){
            cout << p + q << endl;
        }else{
            if(p + r < r + q){
                cout << p + r << endl;
            }else{
                cout << r + q << endl;
            }
        }
    }else if(r + q < p + r){
        if(r + q < p + q){
            cout << r + q << endl;
        }else{
            if(p + r < p + q){
                cout << p + r << endl;
            }else{
                cout << p + q << endl;
            }
        }
    }else{
        if(p + r < p + q){
            cout << p + r << endl;
        }else{
            if(p + q < r + q){
                cout << p + q << endl;
            }else{
                cout << r + q << endl;
            }
        }
    }
    return 0;
}



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

using Int = __int128_t;
Int abs128(Int val){return val<0?-val:val;}

ostream &operator<<(ostream &os,Int val){
  if(ostream::sentry(os)){
    __uint128_t tmp=abs128(val);
    char buf[64];
    char *d=end(buf);
    do{
      --d;
      *d=char(tmp%10+'0');
      tmp/=10;
    }while(tmp);
    if(val<0) *--d='-';
    Int len=end(buf)-d;
    if(os.rdbuf()->sputn(d,len)!=len){
      os.setstate(ios_base::badbit);
    }
  }
  return os;
}

istream &operator>>(istream &is,Int &val){
  string s;
  is>>s;
  val=0;
  for(Int i=0;i<(Int)s.size();i++)
    if(isdigit(s[i])) val=val*10+s[i]-'0';
  if(s[0]=='-') val*=-1;
  return is;
}

Int fib(Int k,const Int mod){
  using arr=vector<Int>;
  using mat=vector<arr>;

  auto mul=[&](const mat &A,const mat &B)->mat{
    mat C(2,arr(2,0));
    for(Int i=0;i<2;i++){
      for(Int j=0;j<2;j++){
	for(Int k=0;k<2;k++)
	  C[i][j]+=A[i][k]*B[k][j];
	C[i][j]%=mod;
      }
    }
    return C;
  };
  
  mat A(2,arr(2,0));
  A[0][0]=A[0][1]=A[1][0]=1;

  mat res(2,arr(2,0));
  res[0][0]=res[1][1]=1;
  
  while(k){
    if(k&1) res=mul(res,A);
    A=mul(A,A);
    k>>=1;
  }
  
  return (res[0][0]+res[0][1])%mod;
};

//INSERT ABOVE HERE
signed main(){
  Int k;
  cin>>k;
  k--;
  
  auto calc=[&](Int x)->Int{
    Int y=(x/2);
    Int res=y*(y+1);
    if(x>y*2) res+=x/2+1;
    return res;
  };
  
  Int l=0,r=1e12;
  while(l+1<r){
    Int m=(l+r)>>1;
    if(calc(m)<=k) l=m;
    else r=m;
  }

  assert(calc(l)<=k);
  assert(calc(r)>k);

  Int a=l/2+1;
  k-=calc(l);
  //cout<<l<<" "<<calc(l)<<":"<<k<<" "<<a<<endl;
  
  const Int MOD = 1e9+7;
  if(k<(a+1)/2){
    cout<<fib(k*2,MOD)*fib(l-k*2,MOD)%MOD<<endl;
    return 0;
  }
  Int b=(a-k)*2-1;
  //cout<<b<<":"<<fib(b,MOD)<<endl;
  //cout<<l-b<<":"<<fib(l-b,MOD)<<endl;
  cout<<fib(b,MOD)*fib(l-b,MOD)%MOD<<endl;
  return 0;
}



Measured memory_bytes: 3196
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    ll N,L;
    cin >> N >> L;
    ll A[N];
    for(ll i = 0; i < N; i++){
        cin >> A[i];
    }
    ll lastKnot = -1;
    for(int i = 1; i < N; i++){
        if(A[i - 1] + A[i] >= L){
            lastKnot = i;
        }
    }
    if(lastKnot != -1){
        cout << "Possible" << endl;
    }else{
        cout << "Impossible" << endl;
        return 0;
    }
    for(int i = 1; i < lastKnot; i++){
        cout << i << endl;
    }
    for(int i = N - 1; i > lastKnot; i--){
        cout << i << endl;
    }
    cout << lastKnot << endl;
}


Measured memory_bytes: 1536
/*
17D8101013F 森田　匡博
JOI0653.cpp 2019/10/31
ID:key4 使用言語:C++
*/

#include <iostream>
#include <cmath>

int main() 
{
  int N;
  std::cin >> N;

  int X[N];
  for(int i = 0; i < N; i++) {
    std::cin >> X[i];
  }

  int M;
  std::cin >> M;

  int A[M];
  for(int i = 0; i < M; i++) {
    std::cin >> A[i];
  }

  for(int i = 0; i < M; i++) {
    X[A[i]-1]++;
    if(X[A[i]-1] == X[A[i]]) {
      X[A[i]-1]--;
    }
    if(X[A[i]-1] >= 2019) {
      X[A[i]-1] = 2019;
    }
  }

  for(int i = 0; i < N; i++) {
    std::cout << X[i] << "\n";
  }

  return 0;
}


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

struct Team {
    int id, point;
    string name;
    bool operator<(const Team& other) const {
        return point == other.point
               ? id < other.id
               : point > other.point;
    }
};

int main() {
    int n;
    bool first = true;

    while (cin >> n, n) {
        Team team[10];
        if (!first) cout << endl; first = false;
        for (int i = 0; i < n; i++) {
            int w, l, d;
            team[i].id = i;
            cin >> team[i].name >> w >> l >> d;
            team[i].point = w*3 + d;
        }
        sort(team, team+n);
        for (int i = 0; i < n; i++) {
            cout << team[i].name << "," << team[i].point << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1216
#include <iostream>
using namespace std;
 
int main() {
string S;
int K;
cin>>K;
cin>>S;
if(S.length()>100||S.length()<=0||K>100||K<=0){return 0;}
if(S.length()<=K){cout<<S<<endl;}
else{
	for(int i=0;i<K;i++){cout<<S[i];}
	cout<<"..."<<endl;
}
 
	return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (unsigned int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD =  1000000007 ;
const int INF = 2000000000;


    int N,A,B,C,D,ans;
    bool F=true;
    string S;
int main(){
    cin>>S;
    S[3]='8';
    cout<<S;
    return 0;

}


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

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n, m = 1000;
	cin>>n;
	ll arr[n];
	for(ll i=0; i<n; i++){
		cin>>arr[i];
	}
	ll s;
	for(ll i=0; i<n-1; i++){
		if(arr[i]>=arr[i+1]){
			continue;
		}
		else{
			s = m/arr[i]; m = m%arr[i];
			m = m+s*arr[i+1];
		}
	}
	cout<<m<<"\n";
	return 0;
}

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

static const int MAX_COUNT = 100;
static int R[MAX_COUNT];



int BubleSort(int* A, int n)
{
	int cnt = 0;
	int flg = 1;
	int tmp;

	while (flg)
	{
		flg = 0;

		for (int i = n - 1; i > 0; i--)
		{
			if (*(A + i - 1) > *(A + i))
			{
				tmp = *(A + i);
				*(A + i) = *(A + i - 1);
				*(A + i - 1) = tmp;
				flg = 1;
				cnt++;
			}
		}
	}

	return cnt;
}


int main()
{
	int n;
	int i;
	int ret;


	cin >> n;

	if (n > MAX_COUNT)
		return -1;

	for (i = 0; i < n; i++)
	{
		cin >> R[i];
	}


	ret = BubleSort(R, n);


	for (i = 0; i < n-1; i++)
	{
		printf("%d ", R[i]);
	}
	printf("%d\n%d\n", R[i], ret);

	return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdio>

using namespace std;

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define each(it,c) for(__typeof(c.begin()) it=c.begin(); it!=c.end(); it++)
#define INF 1<<30
#define mp make_pair
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pair<int, int> > vp;
typedef map<int,int> mpii;
typedef priority_queue<int, vi, greater<int> > pqi;

typedef long long ll;

int main(){
	int n,m; cin>>n>>m;
	vi v(n+1,1);
	vector<bool> b(n+1,false);
	b[1]=true;
	v[0]=0;
	vi x(m);
	vi y(m);
	rep(i,m){
		cin>>x[i]>>y[i];
	}
	bool f = false;
	bool h = false;
	rep(i,m){
		if(x[i]==1 && f==false){
			f = true;
			h=true;
		}
		int s = x[i];
		int t = y[i];
		v[s]--;
		v[t]++;
		if(f){
			if(b[s])b[t]=true;
		}
		if(h){
			if(v[1]==0) b[1] = false;
			h = false;
		}
		if(v[s]==0 && b[s]==true) b[s]=false;

/*
		cout<<i+1<<" "<<s<<" "<<t<<endl;
		rep(i,n+1){
			cout<<v[i]<<" ";
		}
		cout<<endl;
		rep(i,n+1){
			cout<<b[i]<<" ";
		}
		cout<<endl<<endl;
*/
	}
	int cnt=0;
	rep(i,n+1){
		if(0<v[i] && b[i]) cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>>jobs(m);//余裕日数と報酬の二重配列、m日後まで
  rep(i,n){
    int a,b;
    cin>>a>>b;
    if(a>m)continue;//m日後までに終わらなければ、対象外
    jobs[m-a].push_back(b);
    //jobs配列に期限までの余裕日数毎に分類し、報酬を入力
  }
  priority_queue<int>q;//プライオリティ・キューで報酬の最大値を出力
  ll ans=0;//long longなので注意
  for(int i=m-1;i>=0;--i){//後ろからチェックしていく
    for(int b:jobs[i]){//jobs配列から余裕日数毎に報酬を取り出す
      q.push(b);//プライオリティ・キューに入れていく
    }
    if (!q.empty()){//プライオリティ・キューが空になるまで
      ans+=q.top();//i（後ろからの余裕日数）毎の報酬の最大値を取り出す
      q.pop();//最大値を捨てる
    }
  }
  cout<<ans<<endl;    
  return 0;
}

Measured memory_bytes: 5504
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                new_d = k + d
                if distance[v] > new_d:
                    distance[v] = new_d
                    heappush(queue, (new_d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in uvab:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for ans in ans_list[n:0:-1]:
    print(10 ** 15 - ans)


Measured memory_bytes: 133080
import numpy as np
H,N= map(int, input().split())
m = np.array([list(map(int, input().split())) for _ in range(N)])
max_a = np.max(m[:,0])
dp = np.zeros(H+max_a+1, dtype='i8')
for i in range(max_a+1, H+max_a+1):
    dp[i] = np.min(dp[i-m[:,0]] + m[:,1])
print(dp[H+max_a])

Measured memory_bytes: 13028
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int a1,a2,a3;

int main()
{
    while (scanf("%d%d%d",&a1,&a2,&a3)!=EOF)
    {
        int b1=abs(a2-a1)+abs(a3-a2);
        int b2=abs(a3-a1)+abs(a2-a3);
        int b3=abs(a1-a2)+abs(a3-a1);
        int b4=abs(a3-a2)+abs(a1-a3);
        int b5=abs(a1-a3)+abs(a2-a1);
        int b6=abs(a2-a3)+abs(a1-a2);
        int ans=min(b1,min(b2,min(b3,min(b4,min(b5,b6)))));
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    int from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};

int main(){
    CIN(N);
    I vec;
    REP(a,N){
        CIN(b);
        vec.pb(b);
    }
    map<int,int> w,v;

    for(int a = 0;a < N;a++){
        if(a%2 == 0){
            w[vec.at(a)]++;
        }else{
            v[vec.at(a)]++;
        }
    }
    V<P> hoge,huga;
    for(auto a : w){
        hoge.push_back(make_pair(a.second,a.first));
    }
    for(auto a : v){
        huga.push_back(make_pair(a.second,a.first));
    }
    sort(ALL(hoge));
    sort(ALL(huga));
    reverse(ALL(hoge));
    reverse(ALL(huga));
    int ans = INF;
    if(hoge.front().second == huga.front().second){
        if(huga.size() == 1 && hoge.size() == 1){
            ans = N/2;
        }
        if(huga.size() >= 2)ans = min(ans,  N/2 - hoge.front().first + N/2 - huga.at(1).first);
       if(hoge.size() >= 2)ans = min(ans, N/2 - hoge.at(1).first + N/2 - huga.front().first);
    }else{
        ans = N/2-hoge.front().first + N/2-huga.front().first;
    }
    COUT(ans);
    return 0;
}


Measured memory_bytes: 6520
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
#define maxn 100005
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pp;
const long long inf = 2e18;
int n; pp a[maxn]; int ans[maxn];
main(){
	//ios::sync_with_stdio(false); cin.tie(0);
	//freopen(".inp","r",stdin); freopen(".out","w",stdout);
	//freopen("inp.txt","r",stdin);
	cin>>n; int i,j,k;
	for (i=1;i<=n;i++){
		cin>>a[i].first; a[i].second=i;
	}
	sort(a+1,a+n+1);
	i=n; int cur=0,curmin=n+1;
	a[0].first=0;
	while (i>0){
		j=i; curmin=min(curmin,a[j].second);
		while (j>0&&a[j-1].first==a[j].first){
			j--; curmin=min(curmin,a[j].second);
		}
		int pos=curmin,val=a[j].first;
		cur=n+1-j;
		ans[pos]+=cur*(a[j].first-a[j-1].first);
		i=j-1;
	}
	for (i=1;i<=n;i++) cout<<ans[i]<<'\n';
}

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

int main()
{
	LL a, b;
	cin >> a >> b;
	if(a % b == 0) {puts("-1"); return 0;}
	LL ans = ((a * 2) % b == 0) ? (a * 3) : (a * 2);
	cout << ans << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
  int N;
  string S;
  cin >> N >> S;
  int res = 0;
  int x = 0;
  for (int i = 0; i < S.size(); ++i) {
    x += (S[i] == 'I' ? 1 : -1);
    res = max(res, x);
  }
  cout << res << endl;
}

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

using namespace std;

#define frei(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define fred(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define fri(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define frd(i,n) for (int i = (n) - 1; i >= 0; i--)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )

#define uint64 unsigned long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define pr pair

#define BIT(n) (1<<(n))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define sqr(x) ((x) * (x))

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<pii> vii;
typedef vector<int> vi;

#define PI 3.1415926535897932385
#define INF 1000111222
#define eps 1e-7
#define maxN 5005



int main(int argc, char const *argv[])
{
    /* code */
    int n;
    cin >> n;
    int a[n+1][4];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= 3; j++) {
            cin >> a[i][j];
        }
    }
    int dp[n+1][4];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= 3; i++) dp[1][i] = a[1][i];
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= 3; j++) {
            for(int k = 1; k <= 3; k++) {
                if(j != k) {
                    dp[i][j] = max(dp[i][j], a[i][j] + dp[i-1][k]);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= 3; i++) ans = max(ans, dp[n][i]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328
// B.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
	int n, m, x, y, a;
	cin >> n >> m >> x >> y;
	int max_x = x, min_y = y;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		max_x = max(max_x, a);
	}
	for (int i = 0; i < m; ++i) {
		cin >> a;
		min_y = min(min_y, a);
	}
	cout << (max_x < min_y ? "No War" : "War") << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
N, M = map(int, sys.stdin.readline().split())
A = [[1, i] for i in list(map(int, sys.stdin.readline().split()))]
BC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

card_list = A + BC
sorted_cards = sorted(card_list, key=lambda x: x[1], reverse=True)
n = 0
cards_sum = 0
for i in range(N):
    if sorted_cards[i][0] + n <= N:
        cards_sum += sorted_cards[i][1] * sorted_cards[i][0]
        n += sorted_cards[i][0]
    elif n < N and sorted_cards[i][0] + n > N:
        cards_sum += sorted_cards[i][1] * (N - n)
        n = N
        break
    else:
        break

print(cards_sum)

Measured memory_bytes: 47848
#include <stdio.h>
#include <stdlib.h>

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

int main(){
	int N, i;
	scanf("%d", &N);
	int *P = (int *)malloc(sizeof(int) * N);
	int *P_inv = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &P[i]);
		P[i]--;
		P_inv[P[i]] = i;
	}
	int *A = (int *)malloc(sizeof(int) * N);
	int *B = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		B[i] = 0;
	}
	B[0] = 1;
	A[0] = 0;
	for(i = 1; i < N; i++){
		if(P_inv[i - 1] < P_inv[i]){
			A[i] = A[i - 1];
		}
		else{
			A[i] = i;
		}
		B[A[i]]++;
	}
	int Bmax = 0;
	for(i = 0; i < N; i++){
//		printf("B[%d] = %d\n", i, B[i]);
		Bmax = max(Bmax, B[i]);
	}
	printf("%d\n", N - Bmax);
	return 0;
}

Measured memory_bytes: 3328
n = input()
nums = input()
nums = nums.split(" ")

before_num = int(nums[0])

flag = True
for num in nums:
    if before_num == -1:
        before_num = int(num)
        continue

    if before_num == int(num):
        continue
    elif before_num < int(num):
        before_num = int(num) - 1
    else:
        flag = False
        break
    
    
if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 11152
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
using namespace std;

long long int n, m;
vector<long long int> a;

// long long int gcd(long long int a, long long int b)
// {
//   // Everything divides 0
//   if (a == 0)
//     return b;
//   if (b == 0)
//     return a;

//   // base case
//   if (a == b)
//     return a;

//   // a is greater
//   if (a > b)
//     return gcd(a % b, b);
//   return gcd(a, b % a);
// }

unsigned int gcd(unsigned int u, unsigned int v)
{
  // simple cases (termination)
  if (u == v)
    return u;

  if (u == 0)
    return v;

  if (v == 0)
    return u;

  // look for factors of 2
  if (~u & 1)  // u is even
    if (v & 1) // v is odd
      return gcd(u >> 1, v);
    else // both u and v are even
      return gcd(u >> 1, v >> 1) << 1;

  if (~v & 1) // u is odd, v is even
    return gcd(u, v >> 1);

  // reduce larger argument
  if (u > v)
    return gcd((u - v) >> 1, v);

  return gcd((v - u) >> 1, u);
}

int main()
{
  cin >> n >> m;
  a.resize(n);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    a[i] /= 2;
  }

  // a[0]が2で何回割れるか
  long long int divByTwo_0 = 0;
  long long int num = a[0];
  while (num % 2 == 0)
  {
    num /= 2;
    divByTwo_0++;
  }

  // a[0]~a[n-1]は、2で割れる回数が一致していることが半公倍数が存在する必要十分条件
  for (int i = 1; i < n; i++)
  {
    long long int divByTwo_i = 0;
    num = a[i];
    while (num % 2 == 0)
    {
      num /= 2;
      divByTwo_i++;
    }
    if (divByTwo_0 != divByTwo_i)
    {
      cout << 0 << endl;
      return 0;
    }
  }

  // cout << "divByTwo: " << divByTwo_0 << endl;

  long long int min = a[0];
  for (int i = 1; i < n; i++)
  {
    min = min / gcd(min, a[i]) * a[i];
    // for (int j = 1; j <= a[i]; j += 2)
    // {
    //   if (min * j % a[i] == 0)
    //   {
    //     min *= j;
    //     break;
    //   }
    // }
  }

  // cout << "min: " << min << endl;

  num = m / min;
  if (num % 2 == 0)
  {
    num--;
  }
  cout << (num + 1) / 2 << endl;
}


Measured memory_bytes: 1024
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 100000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll n ; cin >> n ;
	vll a(n) ;
	for(auto &i:a) cin >> i ;
	sort(all(a)) ;
	reverse(all(a)) ;
	ll ans = 0 ;
	for(int i=0;i<n-2;i++){
		for(int j=i+1;j<n-1;j++){
			if(a.at(j)*2<=a.at(i)) break ;
			ll l,r,m ;
			l = j ;
			r = n ;
			while(l+1<r){
				m = (l+r)/2 ;
				if(a.at(m)+a.at(j)>a.at(i)) l = m ;
				else r = m ;
			}
			ans += l-j ;
		}
	}
	cout << ans << endl ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    string s,t; cin>>s>>t;
    int ans = 0;
    rep(i,s.length()) {
        if (s[i] != t[i]) ans++;
    }

    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3912
#include <stdio.h>
#include <string.h>

char str1[5000];
char str2[5000];

int main(void) {
	int offset_max;
	int i,j;
	int result,now;
	while(scanf("%s%s",str1,str2)==2) {
		result=0;
		offset_max=strlen(str1)-1;
		for(i=0;i<offset_max;i++) {
			now=0;
			for(j=0;str1[j]!=0 && str2[j+i]!=0;j++) {
				if(str1[j]==str2[j+i])now++;
				else {
					if(result<now)result=now;
					now=0;
				}
			}
			if(result<now)result=now;
		}
		offset_max=strlen(str2)-1;
		for(i=0;i<offset_max;i++) {
			now=0;
			for(j=0;str1[j+i]!=0 && str2[j]!=0;j++) {
				if(str1[j+i]==str2[j])now++;
				else {
					if(result<now)result=now;
					now=0;
				}
			}
			if(result<now)result=now;
		}
		printf("%d\n",result);
	}
	return 0;
}

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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  ll res = INT_MAX;
  for (int i = 1; i < n; i++) {
    ll sum1 = 0, sum2 = 0;
    for (int j = 0; j < i; j++) {
      sum1 += v[j];
    }
    for (int j = i; j < n; j++) {
      sum2 += v[j];
    }
    // cout << sum1 << endl;
    // cout << sum2 << endl;
    res = min(res, abs(sum1 - sum2));
  }

  cout << res << endl;
}


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

const int Max = 1e7;
vector<int> mps(Max+1);

void mpsinit(){//O(NloglogN)
    for(int i = 0; i <= Max; i++) mps[i] = i;
    for(ll i = 2; i*i <= Max; i++){
        if(mps[i] == i){
            for(ll j = i*i; j <= Max; j += i){
                if(mps[j] == j) mps[j] = i;
            }
        }
    }
}
template<typename T>
set<T> prime_factorization(T n){//O(logN)
    set<T> ret;
    while(mps[n] != n){
        ret.insert(mps[n]);
        n = n/mps[n];
    }
    ret.insert(mps[n]);
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    mpsinit();
    map<int,bool> seen;
    bool pc = true;

    for(int i = 0; i < n; i++){
        if(a[i] == 1) continue;
        set<int> fp = prime_factorization(a[i]);
        for(auto p:fp){
            if(seen[p]) pc = false;
            seen[p] = true;
        }
    }

    int g = __gcd(a[0],a[1]);
    for(int i = 0; i < n; i++) g = __gcd(g,a[i]);

    if(pc) cout << "pairwise coprime" << endl;
    else if(g == 1) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
}

Measured memory_bytes: 49932
#include <bits/stdc++.h>
//#define DBG

using namespace std;

long long N;
vector <long long> A;

int main(){
    cin >> N;
    cin.ignore();
    for(int i = 0; i < N; i++){
        long long tmp;
        cin >> tmp;
        A.push_back(tmp);
    }
    cin.ignore();

    sort(A.begin(), A.end());

    // 最初に最大
    long long sum = A[N-1];

    if(N == 2){
        cout << sum << endl;
        return 0;
    }

    // その後は2回ずつ
    vector<bool> acnt (N-1, false);

    int ptr = N - 2;
    for(int i = 0; i < N - 2; i++){
        #ifdef DBG
        printf("i = %d pls A[%d] = %lld\n", i, ptr, A[ptr]);
        #endif
        sum += A[ptr];
        if(acnt[ptr]){
            --ptr;
        } else {
            acnt[ptr] = true;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 5364
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
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; }



int main(int argc, char const *argv[]) {
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  if (k >= n) {
    puts("0");
    return 0;
  }
  sort(all(a));
  reverse(all(a));
  rep(i, k) a[i] = 0;
  ll sum = 0;
  rep(i, n) sum += a[i];
  cout << sum << endl;
  return 0;
}

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


int main(){
    int a,b;
    int d[4]={0};
    for(int i=0;i<3;i++){
        cin>>a>>b;
        a--;
        b--;
        d[a]++;
        d[b]++;
    }
    if(d[0]<=2 && d[1]<=2 && d[2]<=2 && d[3]<=2)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    
    return 0;
}

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

using namespace std;

int main(){

	int n, q, tmp;
  	long long int ans=0;
  	map<int, int> m;

	cin>> n;
	for(int i=0;i<n;i++){
      cin>> tmp;
      if (m.count(tmp)){
        	m[tmp]++;
		}else{
        	m[tmp]=1;
		}
    }

	cin>> q;
	for(int i=0;i<q;i++){
      	cin>> tmp;
      	//if(m.count(tmp)) ans+=m[tmp];
      	if(m.count(tmp)) ans+=1;
    }
      
	cout<< ans << endl;

	return 0;
}



Measured memory_bytes: 7696
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> ABC = Console.ReadLine().Split(" ").Select(x => int.Parse(x)).ToList();
            int K = int.Parse(Console.ReadLine());
            int ans = ABC.Sum();
            int max = ABC.Max();
            ans -= max;
            for(int i = 0; i < K; i++)
            {
                max *= 2;
            }
            Console.WriteLine(ans + max);
        }
    }
}
//int[] N = Console.ReadLine().Split(" ").Select(x => int.Parse(x)).ToArray();

Measured memory_bytes: 28172
N = int(input())
Target =  [0] * N

A = list(map(int, input().split()))
if A[0] != 0 :
    for i in range(A[0]) :
        Target[A[i+1]-1]  += 1

B = list(map(int, input().split()))
if B[0] != 0 :
    for i in range(B[0]) :
        Target[B[i+1]-1] += 2
    
C = list(map(int, input().split()))
if C[0] != 0 :
    for i in range(C[0]) :
        Target[C[i+1]-1] +=4

S = 0
for i in range(N) :
    if Target[i] == 4 or Target[i] == 6 or Target[i] == 7 :
        S += 1

print(S)



Measured memory_bytes: 5604