akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
#define N_ 301000
using namespace std;
long long LD[N_], RD[N_], S[N_], DD[N_];
long long L[N_], R[N_];
int n, top;
struct point{
    long long a, b;
}st[N_];
long long Get(point p, int t){
    return p.a*t+p.b;
}
bool Over1(point a, point b, point c){
    if((b.b-a.b)*(a.a-c.a) <= (c.b-a.b)*(a.a-b.a))return true;
    return false;
}
bool Over2(point a, point b, point c){
    if((a.b-b.b)*(c.a-a.a) >= (a.b-c.b)*(b.a-a.a))return true;
    return false;
}
point MakeL(int i, long long d){
    return {-i, 1ll*i*(i-1)/2 + d + S[i]};
}
point MakeR(int i, long long d){
    return {-i, -S[i-1] + 1ll*i*(i+1)/2 + d};
}
void Do(int b, int e){
    if(b>e)return;
    int m = (b+e)>>1, i;
    top = 0;
    for(i=b-1;i<m;i++){
        point tp = MakeL(i,LD[i]);
        while(top>1 && Over1(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    for(i=m;i<=e;i++){
        while(top>1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        L[i] = Get(st[top],i) - S[i] + 1ll*i*(i+1)/2;
    }
    top = 0;
    for(i=e+1;i>m;i--){
        point tp = MakeR(i,RD[i]);
        while(top>1 && Over2(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    for(i=m;i>=b;i--){
        while(top > 1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        R[i] = Get(st[top],i) + S[i-1] + 1ll*i*(i-1)/2;
    }
    long long MM = -8e18;
    for(i=e;i>=m;i--){
        L[i] = L[i] + RD[i+1];
        MM = max(MM, L[i]);
        DD[i] = max(DD[i], MM);
    }
    MM = -8e18;
    for(i=b;i<=m;i++){
        R[i] = R[i] + LD[i-1];
        MM = max(MM, R[i]);
        DD[i] = max(DD[i], MM);
    }
    Do(b,m-1);
    Do(m+1,e);
}
int main(){
    int i, a, Q, b;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a);
        S[i] = S[i-1] + a;
        DD[i] = -8e18;
    }
    LD[0] = 0;
    st[++top] = {0,0};
    for(i=1;i<=n;i++){
        while(top>1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        LD[i] = max(Get(st[top],i) - S[i] + 1ll*i*(i+1)/2, LD[i-1]);
        point tp = MakeL(i,LD[i]);
        while(top>1 && Over1(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    RD[n+1] = 0;
    top = 0;
    st[++top] = MakeR(n+1,0);
    for(i=n;i>=1;i--){
        while(top > 1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        RD[i] = max(Get(st[top],i) + S[i-1] + 1ll*i*(i-1)/2, RD[i+1]);
        point tp = MakeR(i,RD[i]);
        while(top>1 && Over2(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    Do(1, n);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&a,&b);
        printf("%lld\n",max(LD[a-1] + RD[a+1], DD[a] - b + S[a] - S[a-1]));
    }
}

Measured memory_bytes: 16640
#include <stdio.h>
 
int main() {
 
  int n,m,i,j;
  int a,b;
  int A[100][100] = {0};
  int B[100] = {0};
  int c[100] = {0};
 
  scanf("%d %d " ,&n,&m);
 
  for(j=0; j<n; j++) {
  for(i=0; i < m; i++) {
    scanf("%d",&a);
    A[j][i] = a;
  }
}
 
  for(j=0; j<m; j++) {
    scanf("%d",&b);
    B[j] = b;
  }
 
  for(j=0;j<n ; j++){ 
  for(i = 0; i<m; i++){
     c[j] = c[j] + A[j][i]*B[i];
    }
  }
 
  for(i=0;i<n;i++) {
    printf("%d\n",c[i]);
  }
  return 0;
}


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

int main(){
  string str;
  stack<int> stk;
  int sum;
  
  while(cin>>str){
    if(str=="+" || str=="-" || str=="*"){
      int x=stk.top();
      stk.pop();
      int y=stk.top();
      stk.pop();
      if(str=="+") sum=y+x;
      if(str=="-") sum=y-x;
      if(str=="*") sum=y*x;
      stk.push(sum);
    }
    else{
      int n=stoi(str);
      stk.push(n);
    }
  }
  
  cout<<stk.top()<<endl;
  return 0;
}



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

#define INF 1000000007
#define LINF 1000000000000000007

using namespace std;

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

Int gcd(Int x, Int y){
	if(y == 0)
		return x;
	return gcd(y, x % y);
}

Int lcm(Int x, Int y){
	return x * y / gcd(x, y);
}

bool sosuu(int x){
	bool b = 1;
	if(x == 1) b = 0;
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0) {
			b = 0;
			break;
		}
	}
	return b;
}

Int a,b,c,k;

int main(){
	cin >> a >> b >> c >> k;
	
	if(k % 2 == 0) cout << a -b << endl;
	else cout << b-a << endl;
	
	return 0;
}

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

int main() {
  int N,M;
  cin >> N >> M;
  
  int sum_n =0,sum_m =0;
  
  for(int i =0;i < N;i++){
    sum_n += i;
  }
  for(int i=0;i < M;i++){
    sum_m += i;
  }
      
  cout << sum_n + sum_m << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <utility>
using namespace std;
typedef long long ll;

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

  if(s == "SAT")cout << 1 << endl;
  if(s == "SUN")cout << 7 << endl;
  if(s == "MON")cout << 6 << endl;
  if(s == "TUE")cout << 5 << endl;
  if(s == "WED")cout << 4 << endl;
  if(s == "THU")cout << 3 << endl;
  if(s == "FRI")cout << 2 << endl; 

}

Measured memory_bytes: 256
#if 0
date +%Y.%m.%d

题解先咕着。
#endif
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long lolong;

inline int input() { int x; scanf("%d", &x); return x; }
inline lolong linput() { lolong x; scanf("%lld", &x); return x; }

const int maxn = 200005, maxk = 20;
int min[maxn][maxk], max[maxn][maxk];
int f[maxn];
int a[maxn];

int main() {
	int n = input(), m = input();

	for(int i = 1; i <= n; i ++)
		a[i] = input();

	for(int i = 1; i <= n; i ++)
		if(a[i] > a[i - 1])
			f[i] = f[i - 1] + 1;
		else
			f[i] = 1;

	for(int i = n; i; i --) {
		min[i][0] = max[i][0] = a[i];
		for(int k = 1; k < maxk; k ++) {
			int j = i + (1 << (k - 1));
			min[i][k] = std::min(min[i][k - 1],
					j <= n ? min[j][k - 1] : maxn);
			max[i][k] = std::max(max[i][k - 1],
					j <= n ? max[j][k - 1] : 0);
			/* debug("%d %d %d\n", i, k, st[i][k]); */
		}
	}

	int log = 0;
	while((1 << (log + 1)) <= m)
		log ++;

	/* debug("%d\n", log); */

	int ans = 1;
	bool up = f[m] == m;

	for(int l = 2; l + m - 1 <= n; l ++) {
		int r = l + m - 1;
		/* debug("%d %d\n", std::min(st[l - 1][log], st[r - (1 << log)][log]), */
		/* 		std::min(st[l][log], st[r + 1 - (1 << log)][log])); */
		if(a[l - 1] != std::min(min[l - 1][log], min[r - (1 << log)][log]) or
				a[r] != std::max(max[l][log], max[r + 1 - (1 << log)][log])) {
			/* debug("%d %d\n", l, r); */
			if(!up or f[r] < m)
				ans ++;
		}
		if(f[r] >= m)
			up = 1;
	}

	printf("%d\n", ans);
}


Measured memory_bytes: 33024
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#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 int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool same(int x){
  set<int> s;
  while(x>0){
    s.insert(x%10);x/=10;
  }
  return s.size()==1;
}

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

  int n;
  cin >> n;
  for(int i=n;;i++){
    if(same(i)){
      cout<<i<<endl;
      return 0;
    }
  }


return 0;
}
///....


Measured memory_bytes: 256
#include <functional>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <math.h>
using namespace std;


int main() {
   int n;
   string m;
 
   cin >> n >> m;
  
   if( m.substr(n/2)==m.substr(0,n/2)){
     cout << "Yes" << endl;
   }else{
     cout << "No" << endl;
   }
   
   
  return 0;
}

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

using namespace std;
using Int = long long;

int main(){
    Int N;
    cin >> N;

    for (int i=0; i <= N/7; i++){
        for (int j=0; j<= N/4; j++){
            if ( (4*j + 7*i) == N){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
}

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

using namespace std;

const int INF = 1e9 + 7;

map<long long, string> query;

long long setnum;

string q(string query)
{
  long long num = stoll(query);
  return (num <= setnum == query <= to_string(setnum)) ? "Y" : "N";
}

bool solve()
{
  query.clear();
  long long size, start = 0, last = 10, putN = false;
  while (start < last) {
    long long middle = (start + last) / 2;

    string ans;
    if (query.count(middle)) {
      ans = query[middle];
    } else {
      cout << "? 1" + string(middle, '0') + "\n";
      cout.flush();
      cin >> ans;
      //ans = q('1' + string(middle, '0'));
      query[middle] = ans;
    }
    if (ans == "Y") {
      start = middle + 1;
    } else {
      putN = true;
      last = middle;
    }
  }
  query.clear();
  if(!putN) {
    start = 0, last = 10;
    while (start < last) {
      long long middle = (start + last) / 2;

      string ans;
      if (query.count(middle)) {
        ans = query[middle];
      } else {
        cout << "? 2" + string(middle, '0') + "\n";
        cout.flush();
        cin >> ans;
        //ans = q('2' + string(middle, '0'));
        query[middle] = ans;
      }
      if (ans == "Y") {
        last = middle;
      } else {
        start = middle + 1;
      }
    }
    cout << "! 1" << string(start, '0') << "\n";
    return pow(10LL, start) == setnum;
  }
  query.clear();
  size = start;
  start = pow(10LL, size - 1);
  last = pow(10LL, size) - 1;
  while (start < last) {
    long long middle = (start + last) / 2;

    string res;
    if(query.count(middle)) {
      res = query[middle];
    } else {
      cout << "? " << middle << "0\n";
      cout.flush();
      cin >> res;
      //res = q(to_string(middle * 10));
      query[middle] = res;
    }
    if (res == "Y") {
      last = middle;
    } else {
      start = middle + 1;
    }
  }
  cout << "! " << start << "\n";
  return start == setnum;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  /*for (int i = 1; i <= 1e9; i++) {
    setnum = i;
    if(!solve()) {
      cout << i << "\n";
    }
  }*/
  solve();
}

Measured memory_bytes: 596
#include<stdio.h>
int main(void){
  int a = 0,b = 0,c = 0,i = 0,j = 0;
  scanf("%d %d %d",&a,&b,&c);

  for(i = a;i <= b;i++){
    if( c % i == 0){
      j++;
    }
  }
  printf("%d\n",j);
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;

int n, k; 
int a[N];

bool ok(int mid) {
    int need = 0;
    for (int i = 0; i < n; i++) {
        need += (a[i] - 1) / mid;
    }
    return need <= k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = 1, r = 1e9;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid;
    }
    cout << (ok(l) ? l : r) << "\n";
}

Measured memory_bytes: 4320
// #include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
// #include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), G<type>())
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく、n=10が限界(500 ms)
#define ENDL cout << endl;

const int INF = 2e9;
const LL MOD = 1e9 + 7;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, greater<T> >;
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 debug1(V<T> A){REP(int, i, SIZE(A, int)){if (A[i] == INF) cout << "I ";else cout << A[i] << " ";}ENDL}
template<class T> inline void debug2(VV<T> A){REP(int, i, SIZE(A, int)){REP(int, j, SIZE(A[i], int)){if (A[i][j] == INF) cout << "I "; else cout << A[i][j] << " ";}ENDL}}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  LL ans = 0;
  REP2(int, i, 1, n+1) for (int j = 1; j*i <= n; j++) ans += i*j;
  cout << ans << endl;

  return 0;
}


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

using namespace std;
using ll = long long;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((int)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back

int main()
{
    ll A, B;
    cin >> A >> B;
    if(A == 1 && B == 2) _PR(3);
    else if(A == 2 && B == 1) _PR(3);
    else if(A == 1 && B == 3) _PR(2); 
    else if(A == 3 && B == 1) _PR(2);
    else if(A == 2 && B == 3) _PR(1);
    else if(A == 3 && B == 2) _PR(1);

    return 0;
}

/*



*/

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int N, M; std::cin >> N >> M;
    std::vector<int> liked(M, 0);
    for (int i = 0; i < N; ++i) {
        int K; std::cin >> K;
        for (int j = 0; j < K; ++j) {
            int A; std::cin >> A;
            ++liked[A - 1];
        }
    }
    std::cout << std::count(liked.begin(), liked.end(), N);
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int []l = new int [m];
		int []r = new int [m];
		int maxL = 0;
		int minR = 100000;
		for(int i = 0; i < m ; i++) {
			l[i] = sc.nextInt();
			r[i] = sc.nextInt();
			maxL = Math.max(maxL, l[i]);
			minR = Math.min(minR, r[i]);
			
		}
		if(minR >= maxL) {
		System.out.println((minR - maxL + 1));
		}
		if(minR < maxL) {
	    System.out.println(0);
		}
		

	}

}


Measured memory_bytes: 85312
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;   
#define ll long long
#define ull unsigned long long
// #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> 
ll mod=1e9+7;
#define PI 3.1415926535897932385
#define inf 9e18
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
typedef pair<long long, long long> ii;
#define S second
#define F first
ll max(ll a,ll b){if(a>b){return a;}return b;}
ll min(ll a,ll b){if(a<b){return a;}return b;}
#define MAXN 200005
// Comment this out for interactice problem
// #define endl '\n'
// string to integer stoi() Remember: it takes string not character
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
// To compile--> g++ -std=c++0x -o output one.cpp
// To run--> ./output

int main() 
{ 
    fastio;
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

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

    ll ans=1000;
    ll i = 0; 
    while (i<(n-1)){ 
        while ((i<n-1) && (a[i + 1]<=a[i])) {
            i++;
        }
        if(i ==n-1){
            break; 
        }
        ll b = i;
        i++;
        while ((i < n) && (a[i] >= a[i - 1])) {
            i++; 
        }
        ll s = i-1;
        ll bought_stocks = ans/a[b];
        ll rem = ans%a[b];
        ll sold_money = bought_stocks*a[s];
        ans=sold_money+rem;
    }
    cout<<ans;

    return 0;
}


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

int main()
{
    string S;
    cin >> S;
    if (S <= "2019/04/30") {
        cout << "Heisei" << endl;
    }
    else{
        cout <<  "TBD" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MEM 100001
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef unsigned long long ull;
int n;
main()
{
    sanic; cin.tie(0);
    cin >> n;
    cout << 2*n*3.1415;
}


Measured memory_bytes: 3804
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll n,y;
    cin >> n >> y;
    y /= 1000;
    if(y - n < 0) {
      cout << "-1 -1 -1 "<<endl; return 0;
    }
    ll a,b,c;
    rp(i,2001){
      b = i;
      if((y-n-4*b)%9 != 0) continue;
      if((y-n-4*b) < 0) continue;
      a = (y-n-4*b)/9;
      if(n - a - b < 0) continue;
      c = n - a- b;
      cout << a <<" " << b << " "<<c <<endl;
      return 0;
    }
    cout << "-1 -1 -1 "<<endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
import Control.Applicative ((<$>))
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B
import Data.List
import Data.Function (on)
import Data.Char (isSpace)

main :: IO ()
main = do
  n <- readLn
  solve n <$> getl (readil B.readInt) >>= mapM_ print

solve :: Int -> [(Int,Int)] -> [Int]
solve n xs = map snd $ sort ls'
  where
    ls = sortBy (compare `on` snd) xs
    c = n `div` 2
    lm = snd $ ls !! (c - 1)
    rm = snd $ ls !! c
    ls' = (map (\(i,x) -> (i, rm)) f) ++ (map (\(i,x) -> (i, lm)) b)
    (f, b) = splitAt c ls
    
getl :: (ByteString -> a) -> IO a
getl f = f <$> B.getLine

readil :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> [(Int,a)]
readil f x = unfoldr g (1, x)
  where
    g (i, s) = do
      (n, s') <- f s
      return ((i,n), (i+1, B.dropWhile isSpace s'))


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

int main(){
    string a,b,c;
    cin >> a >> b >> c;
    char diff = 'A' - 'a';
    a[0] += diff;
    b[0] += diff;
    c[0] += diff;
    cout << a[0] << b[0] << c[0] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define nn 65536*48
#define mod 998244353
ll qpow(ll x,ll y=mod-2){
	ll res=1;
	while(y){
		if(y&1) res=res*x%mod;x=x*x%mod;
		y=y/2;
	}
	return res;
}
ll f[nn],rf[nn];ll n,m;
ll C(ll x,ll y){
	if(x>y) return 0;
	return f[y]*rf[x]%mod*rf[y-x]%mod;
}
int main(){
	f[0]=1;for(int i=1;i<nn;i++) f[i]=f[i-1]*i%mod;
	rf[nn-1]=qpow(f[nn-1]);for(int i=nn-2;i>=0;i--) rf[i]=rf[i+1]*(i+1)%mod;

	scanf("%lld%lld",&n,&m);ll ans=0;int k=m+1;ll pre=0;ll flg=0;
	for(int odd=m;odd>=0;odd-=2) if(odd<=n){
		int brick=m+(m-odd)/2;
		ll res=C(n-1,brick+n-1);
		
		if(!flg and brick>=m+1) {
			flg=1;pre=0;
			for(int k=m+1;k<=brick;k++) pre+=C(n-2,brick+n-2-k)*n,pre%=mod;
		}
		else if(brick>=m+1) pre+=C(n-2,brick+n-2-(m+1))*n,pre%=mod;
		
		res-=pre;res%=mod;
		ans=(ans+res*C(odd,n))%mod;
		if(odd) ans-=C(n-2,brick+n-2-m)*n%mod*C(odd-1,n-1)%mod;
	}
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}

Measured memory_bytes: 49536
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().solve();
	}
	
	void solve() {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[]a=new int[n];
		for(int i=0;i<n;i++)a[i]=sc.nextInt()-1;
		
		boolean[]checked=new boolean[n];
		int count=0;
		for(int i=0;i<n;i++) {
			if(checked[i])continue;
			if(a[a[i]]==i) {
				count++;
				checked[a[i]]=true;
			}
			checked[i]=true;
		}
		System.out.println(count);
	}
}

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

using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int h, n, num;
	long long sum = 0;
	cin >> h >> n;
	for(int i = 0; i < n; i++){
		cin >> num;
		sum += num;
	}
	if(sum >= h){
		cout << "Yes";
	} else {
		cout << "No";
	}


}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

/*節点xを根とする部分木の中で最小のキーを持つ節点を返す*/
Node treeMinimum(Node x){
while (x->left != NIL) { x = x->left;}
return x;
}
Node treeSearch(Node u, int k){
if (u == NIL || k == u->key) return u;
if(k < u->key) return treeSearch(u->left,k);
else return treeSearch(u->right,k);
}

/*２分探索木の節点xに次節点がある場合はその次節点を返す
ただし、木の中でxが最大のキーを持つ場合はNILを返す*/
Node treeSuccessor(Node x){
Node y;
if(x->right != NIL) return treeMinimum(x->right);
y = x->parent;
while (y != NIL && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted 
  Node x; // child of y
/*削除する節点yを決定する*/
if(z->left == NIL || z->right == NIL) y = z; /*zが子を最大１つ持つ場合は入力節点のz*/
else y = treeSuccessor(z); /*zが子を２つ持つ場合はzの次節点*/
/*xをyのNILではない子またはyが子を持たない場合はNILを設定*/
if(y->left != NIL) x = y->left;
else x = y->right;
/*yの親とxのポインタを変更しyを削除する*/
if(x != NIL) x->parent = y->parent; /*yが子を１つ持つ場合*/
if(y->parent == NIL) root = x;  /*yが根のときの境界条件の処理*/
else if(y == y->parent->left) y->parent->left = x; /*yが左の子の場合*/
else y->parent->right = x; /*yが右の子の場合*/
/*zの次節点が削除されたときにyの内容をzに移動する。*/
if(y != z) z->key = y->key; 
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

while(x != NIL) {
y = x;
if(z->key < x->key) x = x->left;
else x = x->right;
}
z->parent = y;
if(y == NIL) root = z; //if T is empty
else if(z->key < y->key) y->left = z;
else y->right = z;
}

void inorder(Node u){
if(u != NIL)
{
inorder(u->left);
printf(" %d",u->key);
inorder(u->right);
}
}

void preorder(Node u){
if(u != NIL)
{
printf(" %d",u->key);
preorder(u->left);
preorder(u->right);
}
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
using namespace std;
int n,m;
int F[15][15];
int T[1 << 15];
int G[15][15];
int dp[15][1 << 15];
int DP[2][1 << 15];
int fp[1 << 15];
int gp[1 << 15];
int turn;
vector<int> sm[1 << 15];
int vis[15][1 << 15];
int tot = 0;
int dfs(int pos,int leave){
    if(leave == 0){
        return G[pos][n - 1];
    }
    if(vis[pos][leave] == turn){
        return dp[pos][leave];
    }
    vis[pos][leave] = turn;
    dp[pos][leave] = -1;
    for(int i = 1; i < n; ++i){
        if(leave >> (i - 1) & 1){
            int nxt = dfs(i,leave - (1 << (i - 1)));
            if(nxt == -1 || G[pos][i] == -1)continue;
            dp[pos][leave] = max(dp[pos][leave],nxt + G[pos][i]);
        }
    }
    return dp[pos][leave];
}
int work(int o,int p){
    vector<int> a;
    a.push_back(0);
    for(int i = 0;i < n - 2; ++i){
        if(o >> i & 1){
            a.push_back(i + 1);
        }
    }
    a.push_back(n - 1);
    for(auto &j:sm[p]){
        DP[0][p - j] = T[j * 2 + 1];
    }
    int st = 0;
    for(int i = 1;i < a.size(); ++i){
        st ^= 1;
        memset(DP[st],0,sizeof(DP[st]));
        for(auto &j:sm[p]){
            for(auto &k:sm[j]){
                DP[st][j - k] = max(DP[st][j - k],DP[st ^ 1][j] + T[k * 2 + (1 << a[i])]);
            }
        }
    }
    return DP[st][0];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n; ++i){
        for (int j = 0;j < n; ++j) {
            if(i == j)continue;
            G[i][j] = -1;
        }
    }
    for(int i = 0;i < m; ++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        u--;
        v--;
        tot += w;
        G[u][v] = max(G[u][v],w);
        G[v][u] = max(G[v][u],w);
        if(u > v)swap(u, v);
        F[u][v] += w;
    }
    for(int j = 0;j < (1 << n); ++j){
        for(int i = 0;i < n; ++i){
            if((j >> i & 1) == 0)continue;
            for(int k = i + 1; k < n; ++k){
                if(j >> k & 1){
                    T[j] += F[i][k];
                }
            }
        }
    }
//    for(int i = 0;i < (1 << n);++i){
//        cout << i<<" "<<T[i] << endl;
//    }
    for(int i = 0;i < (1 << n);++i){
        for(int j = 0;j < (1 << n);++j){
            if((j & i) == j)sm[i].push_back(j);
        }
    }
    memset(dp,-1,sizeof(dp));
    memset(vis,-1,sizeof(vis));
    for(int i = 0;i < (1 << (n - 2)); ++i){
        turn = i;
        fp[i] = dfs(0,i);
    }
    int ret = (1 << (n - 2)) - 1;
    int ans = 0;
    for(int i = 0;i < (1 << (n - 2)); ++i){
        if(fp[i] == -1)continue;
        ans = max(ans,fp[i] + work(i,ret - i));
    }
    cout << tot - ans<<endl;
    return 0;
}


Measured memory_bytes: 64896
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
ll gcd(ll a, ll b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n; cin >> n;
	string a, b, c; cin >> a >> b >> c;
	int res = 0;
	rep(i, n)
	{
		if (a[i] != b[i] && b[i] != c[i] && c[i] != a[i])res += 2;
		else if ((a[i] != b[i] && b[i] != c[i]) || (b[i] != c[i] && c[i] != a[i]) || (c[i] != a[i] && a[i] != b[i]))++res;
	}
	cout << res << endl;
}

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

#define REP(n) for (int var = 0; var < n; ++var)

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, k;
    int len = 0;
    cin >> n >> k;
    int l[n];
    for (int i = 0; i < n; ++i) cin >> l[i];
    sort(l, l+n, greater<int>());
    for (int i = 0; i < k; ++i) len += l[i];
    cout << len << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

		if(sb.charAt(0) != 'A') {
			System.out.println("WA");
			return;
		}

		if(sb.indexOf("C") > 1 && sb.indexOf("C") < sb.length()-1) {

		}else {
			System.out.println("WA");
			return;
		}



		sb = sb.replaceFirst("A", "");
		sb = sb.replaceFirst("C", "");


		if(sb.matches("[a-z]+")) {
			System.out.println("AC");
		}else {
			System.out.println("WA");
		}

	}

}


Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N; cin >> N;
    cout << N / 3 << '\n';
}


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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> x(N);
  for(int i=0; i<N; i++){
    cin >> x.at(i);
  }
  int ans=0;
  for(int i=0; i<N; i++){
    ans+= min(2*x.at(i), abs(K-x.at(i))*2);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define  rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long int li;
typedef unsigned long long ull;
typedef vector<int> vi;


int main()
{
    int N,K,X,Y;
    cin>>N>>K>>X>>Y;
    if(N<=K) cout<<X*N<<endl;
    else cout<<X*K+(N-K)*Y<<endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProblemB
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var rNameAndPoints = new List<Tuple<string, int, int>>();

            for (int i = 0; i < N; i++)
            {
                var read = Console.ReadLine().Split(' ').ToArray();
                rNameAndPoints.Add(new Tuple<string, int, int>(read[0], int.Parse(read[1]), i));
            }

            rNameAndPoints = rNameAndPoints.OrderBy(x => x.Item1).ThenBy(x => -x.Item2).ToList();
            foreach (var npi in rNameAndPoints)
                Console.WriteLine(npi.Item3 + 1);
        }
    }
}


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

using ll = long long;
ll modinv(ll a, ll m) {
	assert(m > 0);
	if (m == 1) return 0;
	a %= m;
	if (a < 0) a += m;
	assert(a != 0);
	if (a == 1) return 1;
	return m - modinv(m, a) * m / a;
}

template <int MOD_> struct modnum {
private:
	int v;
public:
	static const int MOD = MOD_;

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}

	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}

	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

using num = modnum<998244353>;

vector<num> fact;
vector<num> ifact;

void init(){
	fact = {1};
	for(int i = 1; i < 11000000; i++) fact.push_back(i * fact[i-1]);
	ifact.resize(fact.size());
	ifact.back() = 1 / fact.back();
	for(int i = (int)fact.size() - 1; i >= 1; i--){
		ifact[i-1] = i * ifact[i];
	}
}

num ncr(int n, int k){
	if(k < 0 || k > n) return 0;
	return fact[n] * ifact[k] * ifact[n-k];
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	init();
	num ans = 1;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) ans *= 3;
	vector<num> p2(n+1, 0);
	p2[0] = 1;
	for(int i = 1; i <= n; i++){
		p2[i] = 2 * p2[i-1];
	}
	for(int i = 0; i < n/2; i++){
		ans -= 2 * p2[i] * ncr(n, i);
	}
	cout << (int)ans << '\n';
}

Measured memory_bytes: 127068
mod = 998244353

A, B, C, D = map(int, input().split())
X = D-B
Y = C-A

# NYI: WHEN X==0 or Y==0
if X==0:
    print(pow(B,Y,mod))
    exit()
    
if Y==0:
    print(pow(A,X,mod))
    exit()  

dp = [B, A]

for x in range(1,X):
    dp.append(dp[-1]*A%mod)

for y in range(1, Y):
    dp_new = [None]*(X+1)
    dp_new[0] = dp[0]*B%mod

    a = 0
    for x in range(1, X+1):
        a = (a+dp[x-1])*(A+y)%mod
        b = dp[x]*(B+x)%mod
        dp_new[x] = (a+b)%mod

    dp = dp_new
        
    
k = 1
ans = 0
for d in dp[::-1]:
    ans += d*k
    ans %= mod
    k *= C
    k %= mod

print(ans)


Measured memory_bytes: 70476
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n,m;
    cin >> n >> m;
    int matrix[100][100]={0,0};
    int row[100]={0};
    int result[100]={0};  //計算結果格納用配列
    for (int i=0; i<n; i++) {  //入力1
        for (int j=0; j<m; j++) {
            cin >> matrix[i][j];
        }
    }
    for (int i=0; i<m; i++) { //入力2
        cin >> row[i];
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            result[i] += matrix[i][j]*row[j];  //行列計算
        }
    }
    for (int i=0; i<n; i++) {
        cout << result[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3152
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stdio.h>
#include <math.h>


using namespace std;

typedef long long ll;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<ll> vll;

typedef pair<int, int> P;

typedef queue<int> qi;
typedef queue<string> qs;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define repp(i, a, b) for(int i = (a); i <= (b); i++)
#define Rep(i, n) for(int i=n; i >= 0; i--)

#define all(v) v.begin(), v.end()
//sort( all(v) )　などと使える




int main(){
    int n; cin >> n;
    vi a(n); rep(i, n) cin >> a[i];
    int q; cin >> q;

    vector<vector<bool>> dp(n+1, vector<bool>(2010, false));
    dp[0][0] = true;
    rep(i, n) rep(j, 2000){
        dp[i+1][j] = dp[i][j] | dp[i+1][j];
        if(j >= a[i]) dp[i+1][j] = dp[i][j-a[i]] | dp[i][j];
    }

    rep(i, q){
        int m; cin >> m;
        cout << (dp[n][m] ? "yes" : "no") << endl;
    }
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVVld = vector<VVld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}

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

int main() {
  int N; cin >> N;
  V cnt(4);
  rep(i, N) {
    int x; cin >> x;
    cnt[x]++;
  }
  
  VVVld dp(N+1, VVld(N+1, Vld(N+1)));

  rep(i3, N+1) rep(i2, N+1) rep(i1, N+1) {
    if (i1 == 0 && i2 == 0 && i3 == 0) continue;
    int sum = i1 + i2 + i3;
    if (sum > N) continue;
    ld r1 = ld(i1)/sum;
    ld r2 = ld(i2)/sum;
    ld r3 = ld(i3)/sum;
    dp[i1][i2][i3] = ld(N)/sum;
    if (i1 > 0) dp[i1][i2][i3] += r1 * dp[i1-1][i2][i3];
    if (i2 > 0) dp[i1][i2][i3] += r2 * dp[i1+1][i2-1][i3];
    if (i3 > 0) dp[i1][i2][i3] += r3 * dp[i1][i2+1][i3-1];
  }

  ld ans = dp[cnt[1]][cnt[2]][cnt[3]];
  cout << setprecision(12);
  cout << ans << endl;
  return 0;
}


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


int main()
{
	ll x;
	cin>>x;
	ll ans=x/11*2;
	x%=11;
	if(x==0)
	{
		cout<<ans<<endl;
		return 0;
	}
	if(x<=6)
	{
		ans++;
	}
	else
	{
		ans+=2;
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

//map<string,bool > passed;
map<string,int> dp;

const int INF=100000000;


int bfs(string str){

	//passed[str]=true;
	set<string> used;
	queue<string> *prv=new queue<string>();
	queue<string> *nxt=new queue<string>();
	int cnt=0;
	prv->push(str);
	while(prv->size()){
		while(prv->size()){
			string s = prv->front();
			prv->pop();
			char cl=s[0];
			bool f=false;
			for(int i = 1; i < s.size(); i++){
				if(s[i]!=cl){
					f=true;
					break;
				}
			}
			if(!f){
				delete prv,nxt;
				return cnt;
			}
			bool flag[200];
			int minCnt=INF;
			for(int i = 0; i < s.size()-1; i++){
				flag['r']=false;
				flag['g']=false;
				flag['b']=false;
				if(s[i]!=s[i+1]){
					flag[s[i]]=true;
					flag[s[i+1]]=true;
					if(!flag['r']){
						string nstr=s;
						nstr[i]='r';
						nstr[i+1]='r';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
						//minCnt=min(minCnt,dfs(nstr)+1);
//						passed[str]=false;
					}
					else if(!flag['g']){
						string nstr=s;
						nstr[i]='g';
						nstr[i+1]='g';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
//						minCnt=min(minCnt,dfs(nstr)+1);
//						passed[str]=false;
					}
					else if(!flag['b']){
						string nstr=s;
						nstr[i]='b';
						nstr[i+1]='b';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
//						passed[str]=true;
	//					minCnt=min(minCnt,dfs(nstr)+1);
	//					passed[str]=false;
					}
				}
			}
		}
		swap(prv,nxt);
		cnt++;
	}
	delete prv,nxt;
	return INF;
}

//int dfs(string str){
//	//if(dp.find(str)!=dp.end()){
//	//	return dp[str];
//	//}
//	if(passed.find(str)!=passed.end()&&passed[str]){
//		return INF;
//	}
////	cout<<str<<endl;
//	char cl=str[0];
//	bool f=false;
//	for(int i = 1; i < str.size(); i++){
//		if(str[i]!=cl){
//			f=true;
//			break;
//		}
//	}
//	if(!f)
//		return 0;
//
//	bool flag[200];
//	int minCnt=INF;
//	for(int i = 0; i < str.size()-1; i++){
//		flag['r']=false;
//		flag['g']=false;
//		flag['b']=false;
//		if(str[i]!=str[i+1]){
//			flag[str[i]]=true;
//			flag[str[i+1]]=true;
//			if(!flag['r']){
//				string nstr=str;
//				nstr[i]='r';
//				nstr[i+1]='r';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//			else if(!flag['g']){
//				string nstr=str;
//				nstr[i]='g';
//				nstr[i+1]='g';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//			else if(!flag['b']){
//				string nstr=str;
//				nstr[i]='b';
//				nstr[i+1]='b';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//		}
//	}
//	//if(minCnt!=INF)
////	dp[str]=minCnt;
//	return minCnt;
//}

int main(){

	string str;
	while(cin>>str&&str!="0"){
		//dp.clear();
		//passed.clear();
		//int ret=dfs(str);
		int ret=bfs(str);
		if(ret!=INF)
			cout<<ret<<endl;
		else
			cout<<"NA"<<endl;
	}


	return 0;
}

Measured memory_bytes: 2320
/* 
* code by: imasnegi
**/

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

#define ll long long
#define nl "\n"
#define spc " "
#define fr(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define vii vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define deb(a) cout << #a << " " << a << nl;

template<typename T>
void printArray(vector<T>& v) {
	for(auto& i : v)
		cout << i << spc;
	cout << nl;
}
const int MaxN = 2e5 + 5;
const int MOD = 1e9 + 7;

ll n; double d;
pair<ll, ll> p[MaxN];

double dist(pair<ll, ll> p) {
	return sqrt((double)(p.first * p.first + p.second * p.second));
}

void solve_cases() {
	cin >> n >> d;
	fr(i, n) cin >> p[i].first >> p[i].second;

	ll cnt = 0;
	fr(i, n) {
		if(dist(p[i]) <= d) cnt++;
	}

	cout << cnt;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cout << setprecision(10) << fixed;
	int t = 1;
	//cin >> t;
	FOR(tt, 1, t) {
		//cout << "Case #" << tt << ": ";
		solve_cases();
	}
}

Measured memory_bytes: 6920
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <time.h>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
using namespace std;

//#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
//#define cin in
//#define cout out
#define pii pair<int,int>
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map

ifstream in("input.txt");
ofstream out("output.txt");

int main()
{
	int k, x;
	cin >> k >> x;

	for (int i = x - k + 1; i <= x + k - 1; i++)
		cout << i << ' ';
	cout << '\n';
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main (String[] args)  {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int q = sc.nextInt();
		TreeSet<Long> sh = new TreeSet<>();
		for (int i = 0; i < a; i++) {
			sh.add(sc.nextLong());
		}
		TreeSet<Long> tm = new TreeSet<>();
		for (int i = 0; i < b; i++) {
			tm.add(sc.nextLong());
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
			long x = sc.nextLong();
			Long leftSH = sh.floor(x);
			Long leftTM = tm.floor(x);
			Long rightSH = sh.ceiling(x);
			Long rightTM = tm.ceiling(x);
			long min = Long.MAX_VALUE;
			if (leftSH != null) {
				if (leftTM != null) {
					min = Math.min(min, x - Math.min(leftSH.longValue(), leftTM.longValue()));
				}
				if (rightTM != null) {
					min = Math.min(min, rightTM.longValue() - leftSH.longValue() + Math.min(x - leftSH.longValue(), rightTM.longValue() - x));
				}
			}
			if (rightSH != null) {
				if (leftTM != null) {
					min = Math.min(min, rightSH.longValue() - leftTM.longValue() + Math.min(x - leftTM.longValue(), rightSH.longValue() - x));
				}
				if (rightTM != null) {
					min = Math.min(min, Math.max(rightSH.longValue(), rightTM.longValue()) - x);
				}
			}
			sb.append(min).append("\n");
		}
		System.out.print(sb);
	}
}


Measured memory_bytes: 110648
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
//#include "MyMath.h"
//#include "MyDisjointset.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
using namespace std;
typedef pair<int, int> P;
const int INF = 2000000000;
class Disjointset {
public:
	vector<int> rank, p;
	Disjointset(int n);
	int find(int x);
	bool same(int x, int y);
	void unite(int x, int y);
};

Disjointset::Disjointset(int n) {
	rank.resize(n, 0);
	for (int i = 0; i < n; i++)
		p.push_back(i);
}
int Disjointset::find(int x) {
	if (x != p[x])
		return p[x] = find(p[x]);
	else return x;
}
bool Disjointset::same(int x, int y) {
	return find(x) == find(y);
}
void Disjointset::unite(int x, int y) {
	int px = find(x);
	int py = find(y);
	if (rank[px] > rank[py]) {
		p[py] = px;
	}
	else {
		p[px] = py;
		if (rank[px] == rank[py]) rank[py]++;
	}
}
struct edge {
	int from, to, cost;
	bool operator < (const edge &e) const {
		return cost > e.cost;
	}
};
int main() {
	int n; cin >> n;
	priority_queue <edge> q;
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
		int c; cin >> c;
		if (c != -1) { edge e; e.from = i; e.to = j; e.cost = c; q.push(e); }
	}
	Disjointset D(n);
	int res = 0;
	while (!q.empty()) {
		edge e = q.top(); q.pop();
		int f = e.from, t = e.to, c = e.cost;
		if (D.same(f, t)) continue;
		res += c;
		D.unite(f, t);
	}
	cout << res << endl;
	return 0;
}

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

int main(){
    
    int N;
    cin >> N;
    int A[N];
    
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    
    int count = 0;
    for(int i=0; i<N-1; i++){
        int minj =i;
        
        for(int j=i; j<N; j++){
            if(A[j] < A[minj]){
                minj =j;
            }
        }
        int x = A[i];
        A[i] = A[minj];
        A[minj] = x;
        
        if(minj != i){
            count++;
        }
    }
    
    for(int k=0; k<N; k++){
        if(k != 0){
            cout << " ";
        }
        cout << A[k];
    }
    cout << endl;
    
    cout << count << endl;
    
    return 0;
}


Measured memory_bytes: 3096