akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <tuple>
#include <cassert>

using namespace std;

using int64 = long long;

const int64 INF = (1LL<<60);

int N;
vector<vector<int>> g;

vector<int> color[2];

void dfs(int v, int p, int col) {
    color[col].push_back(v);
    for (auto el : g[v]) {
        if (el != p) {
            dfs(el, v, (col + 1) & 1);
        }
    }
}

void Exit() {
    cout << "-1\n";
    exit(0);
}

int main() {
    cin >> N;
    g.resize(N);

    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(0, 0, 0);

    int n0 = color[0].size();
    int n1 = color[1].size();

    int v[3] = {0, 0, 0};

    for (int i = 1; i <= N; i++) {
        v[i % 3]++;
    }

    int mv = min(v[1], v[2]);

    if (n0 > n1) {
        swap(color[0], color[1]);
        swap(n0, n1);
    }

    // vector<int> order;

    // for (int i = 3; i <= N; i += 3)
    //     order.push_back(i);

    // if (v[1] > v[2]) {
    //     for (int i = 1; i <= N; i += 3)
    //         order.push_back(i);
    //     for (int i = 2; i <= N; i += 3)
    //         order.push_back(i);        
    // } else {
    //     for (int i = 2; i <= N; i += 3)
    //         order.push_back(i);
    //     for (int i = 1; i <= N; i += 3)
    //         order.push_back(i);
    // }

    vector<int> filler;
    for (int i = 3; i <= N; i += 3)
        filler.push_back(i);

    int x1 = 1, x2 = 2;

    if (v[1] < v[2]) {
        swap(v[1], v[2]);
        swap(x1, x2);
    }

    vector<int> p(N, -1);

    //cerr << v[0] << " " << v[1] << " " << v[2] << "\n";
    //cerr << n0 << " " << n1 << "\n";


    int idx0 = 0;
    int idx1 = 0;
    int idxf = 0;

    if (n0 <= v[0]) {
        cerr << "!\n";
        for (int i = 0; i < n0; i++) {
            p[ color[0][idx0++] ] = filler[idxf++];
        }

        for (int i = idxf; i < v[0]; i++) {
            p[ color[1][idx1++] ] = filler[idxf++];
        }

        for (int i = 0; i < v[1]; i++) {
            p[ color[1][idx1++] ] = 3 * i + 1;
        }

        for (int i = 0; i < v[2]; i++) {
            p[ color[1][idx1++] ] = 3 * i + 2;
        }
    } else {
        if (v[2] > n0 || v[1] > n1)
            Exit();


        for (int i = 0; i < v[2]; i++) {
            //cerr << color[idx0++] << " " << 3 * i + x2 << "\n";
            p[ color[0][idx0++] ] = 3 * i + x2; 
        }

        for (int i = v[2]; i < n0; i++) {
            p[ color[0][idx0++] ] = filler[idxf++];
        }

        //

        for (int i = 0; i < v[1]; i++) {
            p[ color[1][idx1++] ] = 3 * i + x1; 
        }

        for (int i = v[1]; i < n1; i++) {
            p[ color[1][idx1++] ] = filler[idxf++];
        }
    }

    assert(idx0 == n0);
    assert(idx1 == n1);
    assert(idxf == filler.size());

    for (int i = 0; i < N; i++)
        cout << p[i] << " ";
    cout << "\n";

    return 0;
}

Measured memory_bytes: 20724
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<map>
#include<set>
#define ll long long int
 
using namespace std;
 
int n,k;
int a[2500];
int b[2500];
vector < vector <int > >graph;
vector <vector<int > >diameter;
bool used[2500];
void dfs (vector<vector<int > > &graph, vector<int > &d, int v = 1 ,int par = -1 , int depth = 0 ){
  //used[v] = 1;
  d[v] = depth;
  for(int i=0;i<graph[v].size();i++){
    int to = graph[v][i];
    if(to!=par){
      dfs(graph,d,to, v ,depth+1);
      //cout<<"dfs called " <<to<<endl;
    }
  }
}
int main() {
  cin>>n>>k;
  graph.resize((n+1)*(n+1));
  for(int i=0;i<n-1;i++){
    cin>>a[i]>>b[i];
    graph[a[i]].push_back(b[i]);
    graph[b[i]].push_back(a[i]);
  }
  for(int i=1;i<=n;i++){
    //cout<<i<<" : ";
    for(int j=0;j<graph[i].size();j++){
      if(graph[i][j]){
       //cout<<graph[i][j]<<" ";
      }
    }
    //cout<<endl;
  }
  vector<vector<int> >diameter(n+1,vector<int>(n+1,0));
  for(int i=1;i<=n;i++){
    //cout<<"cur node "<<i<<endl;
    dfs(graph,diameter[i],i,-1,0);
  }
 
  int mx = 0;
  for(int i=1;i<=n;i++){
    //cout<<i<<" :: ";
    for(int j=0;j<diameter[i].size();j++){
      //cout<<diameter[i][j]<<" ";
      mx = max(mx,diameter[i][j]);
    }
    //cout<<endl;
  }
  if(mx<=k){
    cout<<0<<endl;
    return 0;
  }
  int res = 2000000;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=n;j++){
      if(diameter[i][j]==k){
        //cout<<i<<" "<<j<<endl;
        int cnt = 0;
        for(int kk=0;kk<=n;kk++){
          if(diameter[i][kk]>k || diameter[j][kk]>k )
            cnt++;
        }
          res = min(res, cnt);
      }
    }
  }
  cout<<res<<endl;
  return 0;
}

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

using ll = long long;

const ll N = 2005, MOD = 1e9 + 7;
ll bit[N];

ll query(ll i){
  ll sum = 0;
  for (; i > 0; i -= i&-i)
    sum += bit[i];
  return sum;
}
void update(ll i, ll val){
  for (; i < N; i += i&-i)
    bit[i] += val;
}

ll count_inversion(const std::vector<ll>& a) {
  memset(bit, 0, sizeof bit);

  ll inv = 0;
  ll total = 0;
  for (const ll& elem : a) {
    //query
    ll greater_than = total - query(elem);
    inv += greater_than;
    
    //update
    total++;
    update(elem, 1);
  }

  return inv;
}

ll sum(ll n) {
  n %= MOD;
  return (n + 1) % MOD * n % MOD * 500000004L % MOD;
}

int32_t main() {
  ll n, k;
  scanf("%lld%lld", &n, &k);

  std::map<ll, ll> freq;
  std::vector<ll> a(n);

  for (ll& elem : a) {
    scanf("%lld", &elem);
    freq[elem]++;
  }

  ll self_inv = count_inversion(a);
  ll to_next = 0;

  ll less_than = 0;
  for (const auto& elem : freq) {
    to_next += less_than * elem.second;
    less_than += elem.second;
  }

  self_inv %= MOD;
  to_next %= MOD;

  ll total_self = self_inv * k % MOD;
  ll meta_pairs = sum(k-1);
  ll total_to_next = meta_pairs * to_next % MOD;
  ll ans = (total_self + total_to_next) % MOD;

//  printf("self_inv: %lld\n", self_inv);
//  printf("to_next: %lld\n", to_next);
 // printf("meta_pairs: %lld\n", meta_pairs);
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair <int,int> PAIR;
const int maxn = 2e5 + 7;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
double a[maxn];

int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	a[0] = 0;
	for(int i = 1;i <= n;++i){
		double x;
		scanf("%lf",&x);
		a[i] = a[i-1] + x;
	}
	for(int i = 2;i+k <= n+1;++i){
		int id = i+k-1;
		double l = a[id-1] - a[i-2];
		double r = a[id] - a[i-1];
		
		if(r-l > eps) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
} 

Measured memory_bytes: 5288
def calc_total_D(stats, D, color):
    total = 0
    for i in range(3):
        y = color[i]
        for x in range(len(stats[i])):
            total += stats[i][x] * D[x][y]
    return total


def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    c = [list(map(int, input().split())) for _ in range(N)]

    # color -= 1
    stats = [[0] * C for _ in range(3)]

    for i in range(N):
        for j in range(N):
            stats[(i+j) % 3][c[i][j]-1] += 1

    retval = float("inf")
    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c1 == c3 or c2 == c3:
                    continue
                retval = min(retval, calc_total_D(stats, D, [c1, c2, c3]))
    print(retval)


if __name__ == "__main__":
    main()


Measured memory_bytes: 44764
<?php
list($w,$h,$n)=fscanf(STDIN,"%d %d %d");
$directionx=array(0,$w);
$directiony=array(0,$h);
for($i=0;$i<$n;++$i){
    list($x,$y,$a)=fscanf(STDIN,"%d %d %d");
    switch ($a) {
        case 1:
            $directionx[0]=max($directionx[0],$x);
            break;
        case 2:
            $directionx[1]=min($directionx[1],$x);
            break;
        case 3:
            $directiony[0]=max($directiony[0],$y);
            break;
        case 4:
            $directiony[1]=min($directiony[1],$y);
            break;
    }
}
$xside=$directionx[1]-$directionx[0];
$yside=$directiony[1]-$directiony[0];
if($xside>0&&$yside>0){
    echo $xside*$yside;
}else{
    echo 0;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

constexpr int MOD = 1e9+7;

int main() {

  int H, W;
  cin >> H >> W;
  vector<string> G(H);
  rep(i, H) cin >> G[i];

  ll ans = 0;

  rep(C, W - 1) {
    static int dp[303][303];
    static int h[303][303];
    rep(i, 303) rep(j, 303) h[i][j] = dp[i][j] = inf;
    rep(i, 303) h[0][i] = h[i][0] = 0;
    dp[0][0] = 0;

    rep(a, H) rep(b, H) {
      h[a+1][b+1] = min(h[a+1][b+1], h[a][b] + (G[a][C] == G[b][C+1]));
    }

    rep(i, H + 1) rep(j, H + 1) {
      dp[i+1][j] = min(dp[i+1][j], dp[i][j] + h[H - i][H - j]);
      dp[i][j+1] = min(dp[i][j+1], dp[i][j] + h[H - i][H - j]);
    }
    ans += dp[H][H];
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;

int main() {
  int h, w;
  cin >> h >> w;
  V<string> g(h);
  rep(i, h) cin >> g[i];

  V<int> his;
  for (char c = 'a'; c <= 'z'; c++) {
    int cnt = 0;
    rep(i, h) rep(j, w) {
      if (g[i][j] == c) cnt++;
    }
    if (cnt > 0) his.push_back(cnt);
  }
  int n = his.size();

  int div4(0), div2(0), div1(0);
  rep(i, n) if (his[i] % 4 == 0) div4++;
  rep(i, n) if (his[i] % 4 != 0 && his[i] % 2 == 0) div2++;
  rep(i, n) if (his[i] % 2 != 0) div1++;

  bool ans = true;
  if (h % 2 == 0 && w % 2 == 0) {
    if (div1 > 0 || div2 > 0) ans = false;
  } else if ((h + w) % 2 != 0) {
    int lim = 0;
    if (h % 2 == 0) {
      lim = h / 2;
    } else {
      lim = w / 2;
    }
    if (div1 > 0) ans = false;
    if (div2 > lim) ans = false;
  } else {
    if (div1 != 1) ans = false;
    if (div2 > h / 2 + w / 2) ans = false;
  }

  cout << ((ans) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3648
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
"""
import sys


def find_square(data):
    max_size = 0
    lmap = []
    for row in data:
        temp = [0]
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)
        temp = [0]

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x in range(1, len(lmap[0])):
            if curr_row[x] == 1:
                if prev_row[x-1] != 0 and prev_row[x] != 0 and curr_row[x-1] != 0:
                    curr_row[x] = min(prev_row[x-1], min(prev_row[x], curr_row[x-1])) + 1
                    if curr_row[x] > max_size:
                        max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>

using namespace std;
using ll = long long;


vector<int> c;
vector<vector<int>> s;
int D;
vector<int> v;
vector<set<int>> U;

ll calc(){
    ll ans = 0;
    vector<int> last(26, 0);
    for(int i = 0;i < D;i++){
        last[v[i] - 1] = i + 1;
        ans += s[i][v[i] - 1];
        //cout<<s[i][v[i] - 1]<<endl;
        for(int j = 0;j < 26;j++){
            ans -= (ll)(i + 1 - last[j]) * c[j];
        }
    }
    return ans;
}

int retrnd(int n){ //乱数生成                                    
	std::random_device rnd;
    std::mt19937 mt(rnd());
    std::uniform_int_distribution<> rand100(0, n);
    return rand100(mt);
}

int main(){
    cin >> D;
    for(int i = 0;i < 26;i++){
        int a;cin >> a;
        c.push_back(a);
    }
    for(int i = 0;i < D;i++){
        vector<int> a;
        for(int j = 0;j < 26;j++){
            int b;cin >> b;
            a.push_back(b);
        }
        s.push_back(a);
    }
    U = vector<set<int>>(26);
    for(int i = 0;i < D;i++){
        v.push_back(retrnd(25) + 1);
    }
    int now = calc();
    int try_cnt = 1000;
    for(int cnt = 0;cnt < try_cnt;cnt++){
        int rnd = retrnd(D - 1);
        for(int i = 1;i < 27;i++){
            int prev = v[rnd];
            v[rnd] = i;
            int w = calc();
            if(now > w){
                v[rnd] = prev;
            }else{
                now = w;
            }
        }
    }
    for(int i = 0;i < D;i++){
        cout<<v[i]<<endl;
    }
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

int f[99][50];
int dp[99][50];
bool debug = true;

int main(void){
	string str;
	int i=0,j=0,tmp;
	
	while(getline(cin,str)){
		istringstream iss(str);
		
		j=0;
		while(iss >> tmp){
			iss.ignore();
			f[i][j] = tmp;
			//if(debug) printf("f[%d][%d] = %d\n",i,j,f[i][j]);
			j++;
		}
		i++;
	}
	
	int row = i-1;
	dp[0][0] = f[0][0]; //dp[i][j] := maximal number of i-th row's j-th column
	for(int i=1;i<=row/2;i++){ //upeer half
		for(int j=0;j<=i;j++){
			if(j==0){
				dp[i][j] = f[i][j] + dp[i-1][j];
			}else if(j==i){
				dp[i][j] = f[i][j] + dp[i-1][j-1];
			}else{
				dp[i][j] = f[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
			}
		}
	}
	for(int i=row/2+1;i<=row;i++){ //lower half
		for(int j=0;j<=row-i;j++){
			dp[i][j] = f[i][j] + max(dp[i-1][j], dp[i-1][j+1]);
		}
	}
	
	cout << dp[row][0] << endl;
}

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

#define REPI(i, n) for(int i = 0; i < n; i++)
#define REPJ(j, n) for(int j = 0; j < n; j++)

using ll = long long;
using namespace std;

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

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

    REPI(i, a * 2 - 1){
        cout << b - a + 1 + i << ' ';
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  vector<int>a(m);
  
  for(int i=0;i<m;i++)cin>>a[i];
  
  if(n>=m)
  {
    cout<<0<<endl;
    return 0;
  }
  sort(a.begin(),a.end());
  
  vector<int>d(m-1);
  long long  sum=0;
  for(int i=0;i<m-1;i++)
  {
    d[i]=abs(a[i]-a[i+1]);
    sum+=d[i];
  }
  
  sort(d.begin(),d.end());
  int j=m-2;
  while(n>1)
  {
    sum-=d[j--];
    n--;
  }
 cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>

using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define rrep(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i, x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
#define put2darr(arr, row, col) rep(i, row) { rep(j, col) { printf("%18d", arr[i][j]); } cout << endl; }

using namespace std;

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

/* 1..10
 * rep:   0 1 2 3 4 5 6 7 8 9
 * reps:  1 2 3 4 5 6 7 8 9 10
 * rrep:  9 8 7 6 5 4 3 2 1 0
 * rreps: 10 9 8 7 6 5 4 3 2 1
 */
int h[100010];
int main(){
    int ans = 0, tmp = 0;
    int n;
    cin >> n;
    rep(i, n) cin >> h[i];
    int s  = h[0];
    reps(i, n-1){
        if(h[i-1] >= h[i]) tmp++;
        else {
            chmax(ans, tmp);
            tmp = 0;
        }
        if(i ==  n-1) chmax(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define vc vector<int>
#define um unordered_map<int,int>
#define ll long long 
#define rep(i,a,b) for(__typeof(a) i=a; i<b; i++)
#define si(a) a.size()
#define all(a) a.begin(),a.end()
#define ss(a) a.second
#define ff(a) a.first
#define M 1000000
#define pb push_back
#define repit(i,a) for(auto i=a.begin(); i!=a.end(); i++)
#define take(arr,n) for(int i=0;i<n;i++)cin>>arr[i]
#define out(arr,n) for(int i=0;i<n;i++)cout<<arr[i]<<' '
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define reprev(i,b,a) for(__typeof(b) i=b; i>=a; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define doublearray vector<vector<int>>
using namespace std;
ll max(ll a, ll b){ return a>b?a:b; }
ll min(ll a, ll b){ return a<b?a:b; }
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}
ll ans(ll a){
    return a<0?a+MOD:a;
}
double distance(double a, double b){
  return sqrt(pow(a,2)+pow(b,2));
}
int main(){
  int n; double d;  cin>>n>>d; int count=0;
  rep(i,0,n){
    double x, y; cin>>x>>y;
    if(distance(x,y)<=d) count++;
  }
  cout<<count<<endl;
}





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

#define LL long long
#define ULL unsigned long long

#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(l,r) (((l)+(r))>>1)

const int MOD = (int) 1e9 + 7;
const double eps = (double) 1e-8;
const int maxn = (int) 3e5 + 20;
const double pi = (double) acos(-1.0);

void work()
{
    int n, k;
    string s;
    cin >>n >>k;
    cin >>s;
    s[k - 1] += 32;
    cout <<s <<endl;
}


int main()
{
#ifdef yukihana0416
freopen("in.txt", "r" ,stdin);
//freopen("out.txt", "w", stdout);
#endif // yukihana0416

    int tc = 1;
//    scanf("%d", &tc);
    for(int ca = 1; ca <= tc; ca++)
    {
//        printf("Case #%d: ", ca);
        work();
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=100010;

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

Formula:

ci-> count of number i

E[c1][c2][c3] = 1(for current move) + (n-(c1+c2+c3))/n * E[c1][c2][c3] + (c1/n)*E[c1-1][c2][c3] + (c2/n)*E[c1+1][c2-1][c3] + (c3/n)*E[c1][c2+1][c3-1]

                                         prob of picking 0                  prob of picking 1      prob of picking 2          prob of picking 3

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

ll n;
ll ar[301];

long double dp[301][301][301];

long double func(ll c1,ll c2,ll c3)
{
    //cout<<c1<<" "<<c2<<" "<<c3<<endl;
    if(c1==0&&c2==0&&c3==0){return 0.0;}
    if(dp[c1][c2][c3]==-1){
    long double ans=0;
    if(c1>0&&c2>0&&c3>0)
    {
        ans=(n*1.0/(c1+c2+c3)) + (c1*1.0/(c1+c2+c3))*func(c1-1,c2,c3) + (c2*1.0/(c1+c2+c3))*func(c1+1,c2-1,c3) + (c3*1.0/(c1+c2+c3))*func(c1,c2+1,c3-1);
    }
    else if(c1>0&&c2>0)
    {
        ans=(n*1.0/(c1+c2)) + (c1*1.0/(c1+c2))*func(c1-1,c2,c3) + (c2*1.0/(c1+c2))*func(c1+1,c2-1,c3);
    }
    else if(c1>0&&c3>0)
    {
        ans=(n*1.0/(c1+c3)) + (c1*1.0/(c1+c3))*func(c1-1,c2,c3) + (c3*1.0/(c1+c3))*func(c1,c2+1,c3-1);
    }
    else if(c2>0&&c3>0)
    {
         ans=(n*1.0/(c2+c3)) + (c2*1.0/(c2+c3))*func(c1+1,c2-1,c3) + (c3*1.0/(c2+c3))*func(c1,c2+1,c3-1);
    }
    else if(c1>0)
    {
        ans=(n*1.0/(c1)) + func(c1-1,c2,c3);
    }
    else if(c2>0)
    {
        ans=(n*1.0/(c2)) + func(c1+1,c2-1,c3);
    }
    else if(c3>0)
    {
        ans=(n*1.0/(c3)) + func(c1,c2+1,c3-1);
    }
    dp[c1][c2][c3]=ans;
    }
    return dp[c1][c2][c3];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //freopen("output.txt","w",stdout);

    cin>>n;
    ll c1=0,c2=0,c3=0;
    for(ll i=0;i<n;++i){
        cin>>ar[i];
        if(ar[i]==1){++c1;}
        if(ar[i]==2){++c2;}
        if(ar[i]==3){++c3;}
    }

    for(ll i=0;i<=n;++i){
        for(ll j=0;j<=n;++j){
            for(ll k=0;k<=n;++k)
            {
                dp[i][j][k]=-1;
            }
        }
    }

    long double ans=func(c1,c2,c3);
    cout<<std::fixed;
    cout<<setprecision(9);
    cout<<ans<<endl;


    return (0);
}


Measured memory_bytes: 426496
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        long k=sc.nextLong();
  		long a=n%k;
  		long b=k-a;
		long c=Math.min(a,b);
  		long ans=Math.min(c,n);
   

    	System.out.println(ans);
    }
}



Measured memory_bytes: 23764
n = int(input())
a = list(map(int, input().split()))

if sum(a) % (n * (n+1) // 2) != 0:
    print("NO")
    exit()

k = sum(a) // (n * (n+1) // 2)
b = [0] * n
for i in range(n-1):
    b[i] = a[i+1] - a[i]
b[n-1] = a[0] - a[n-1]

for i in range(n):
    b[i] -= k

count = 0
for nb in b:
    if (-nb % n) != 0 or nb > 0:
        print("NO")
        exit()
    count += -nb // n

if count == k:
    print("YES")
else:
    print("NO")


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

namespace _0516
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                if (x[0] == 0 && x[1] == 0)
                {
                    break;
                }
                int[] n = new int[x[0]];
                for (int i = 0; i < x[0]; i++)
                {
                    n[i] = int.Parse(Console.ReadLine());
                }
                int a = 0;
                int now = 0;
                for (int i = 0; i < x[1]; i++)
                {
                    now += n[i];
                }
                if (a <= now)
                {
                    a = now;
                }
                for (int i = 1; i < x[0] - x[1] + 1; i++)
                {
                    now -= n[i - 1];
                    now += n[i + x[1] - 1];
                    if (a <= now)
                    {
                        a = now;
                    }
                }
                Console.WriteLine(a);
            }
        }
    }
}

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

using namespace std;
typedef long long ll;

const int N = 100005;

int main(){
    int k, a, b;

    scanf("%d %d %d", &k, &a, &b);

    if(b <= a + 2){
        printf("%d\n", k + 1);
        return 0;
    }

    if(k <= a){
        printf("%d\n", k + 1);
        return 0;
    }

    ll tot = a;

    k -= a - 1;

    tot += 1LL * (k / 2) * (b - a);
    k %= 2;
    if(k) tot++;

    printf("%lld\n", tot);
}


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

using namespace std;

using i64 = int64_t;

int main() {
#ifdef GOLIKOV
  freopen("in", "rt", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  struct item {
    int w, s, v;
  };
  vector<item> a(n);
  for (auto& x : a) {
    cin >> x.w >> x.s >> x.v;
  }

  sort(a.begin(), a.end(), [](auto& x, auto& y) {
    return x.w + x.s < y.w + y.s;
  });
  int const W = (int) 2e4 + 20;

  vector<i64> answer(W + 1);
  for (auto& x : a) {
    for (int w = min(x.s, W - x.w); w >= 0; --w) {
      answer[w + x.w] = max(answer[w + x.w], answer[w] + x.v);
    }
  }
  cout << (*max_element(answer.begin(), answer.end())) << '\n';
  return 0;
}

Measured memory_bytes: 384
/*
   Created by Rahul Goel.
*/
/*******************************************************************************/
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
/*******************************************************************************/
using namespace std;
using ll = long long;
using ld = long double;
ll mod = 998244353;
const int INF = 1e9;
const ll LINF = 1e18;
/*******************************************************************************/
/*
.-.. . -. -.- .- / .. ... / .-.. --- ...- . -.-.--
 */
/* For PBDS */
/*Two new methods X.order_of_key() and X.find_by_order()*/
/*
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

/*******************************************************************************/
ll mod_sum() { return 0LL; }
template<typename T, typename... Args>
T mod_sum(T a, Args... args) { return ((a + mod_sum(args...))%mod + mod)%mod; }

ll mod_prod() { return 1LL; }
template<typename T, typename... Args>
T mod_prod(T a, Args... args) { return (a*mod_prod(args...))%mod; }
/*******************************************************************************/
using pii = pair < ll, ll >;
using vi = vector < ll >;
using vb = vector < bool >;
using vvi = vector < vector < ll > >;
using vvb = vector < vector < bool > >;
using vpii = vector < pii >;
using vvpii = vector < vector < pii > >;
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define fastio          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(c)          (c).begin(), (c).end()
#define present(c,x)    ((c).find(x) != (c).end())
#define cpresent(c,x)   (find(all(c),x) != (c).end())
#define uniq(c)         (c).resize(distance((c).begin(), unique(all(c))))
#define min_pq(t)       priority_queue < t, vector < t >, greater < t > >
#define max_pq(t)       priority_queue < t >
#define pb              push_back
#define ff              first
#define ss              second
/*******************************************************************************/

/*
    Code begins after this.
*/


ll solve(){
    ll n, s;
    cin >> n >> s;
    vi a(n+1);
    for(ll i=1; i<=n; i++)
        cin >> a[i];
    vvi dp(n+1, vi(s+1));
    dp[0][0] = 1;
    for(ll i=1; i<=n; i++){
        for(ll j=0; j<=s; j++){
            dp[i][j] = (dp[i-1][j]*2)%mod;
            if(j-a[i] >= 0)
                dp[i][j] = (dp[i-1][j-a[i]] + dp[i][j]) % mod;
        }
    }
    cout << dp[n][s] << endl;
    return 0;
}


signed main(){
    fastio;

    ll t = 1;
    while(t--)
        solve();

    return 0;
}

/*******************************************************************************/
// Remeber - In a custom comparator cmp(a, b) a==b must always return to false.


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

int main()
{
	char c;
	int nI[27] = { 0 };
	while (cin >> c)
	{
		int n = tolower(c);
		nI[n - '`'] += 1;
	}
	for (int i = 1; i < 27; i++)
	{
		printf("%c : %d\n", '`' + i, nI[i]);
	}
	//system("pause");
	return 0;
}

Measured memory_bytes: 3156
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
        int w = in.nextInt();
       
      int[] wa = new int[n];
      long[] va = new long[n];
      
      for(int i=0;i<n;i++){
         wa[i]=in.nextInt();
         va[i]=in.nextInt();
      }
      
      long[][] dp = new long[n+1][w+1];
      
      for(int i=1;i<=n;i++){
          for(int j=1;j<=w;j++){
            
            dp[i][j]=dp[i-1][j];
            
            if(j>=wa[i-1]){
                 dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-wa[i-1]]+va[i-1]);
            }
          }
      }
      
      System.out.print(dp[n][w]);
      
      
	}
}

Measured memory_bytes: 127444
from sys import stdin
input=stdin.readline().rstrip()

#あえて文字列で
num_list=[input[x] for x in range(len(input))]
output=0
n=len(input)-1
#2**nの全パターンを探索
for i in range(2**n):
    #s_nowは"1+23"みたいになるイメージなので先頭の数字を入れておく
    s_now=num_list[0]
    #2進数表記なので最大n回右にずらせる
    for j in range(n):
        #bit演算　iを2進数表記し、j個分右にずらしてそこが1ならTrueを返す
        if ((i >> j) & 1):
            #1が入っているなら＋を書く 01(1)なら"12+3"、11(3)なら"1+2+3"となるようなイメージ
            s_now+=("+")
        #次の数字を書く
        s_now+=(num_list[j+1])

    #print(s_now)
    #eval:文字列を式として計算してくれる
    output+=eval(s_now)

print(output)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inS = Console.ReadLine().Split(' ');
            int N = int.Parse(inS[0]);
            int M = int.Parse(inS[1]);

            int left = 0;
            int right = int.MaxValue;


            for(int i = 0; i < M; i++)
            {
                string[] s2 = Console.ReadLine().Split(' ');
                int l = int.Parse(s2[0]) - 1;
                int r = int.Parse(s2[1]);

                left = Math.Max(left, l);
                right = Math.Min(right, r);
            }

            Console.WriteLine(Math.Max(right - left, 0));
        }
    }
}


Measured memory_bytes: 17212
#include<iostream>
#include<string>
#include<climits>
#include<vector>
#include <sstream>
#include<algorithm>
#include<array>
#include<map>

using namespace std;


int main(void) {

	string s;
	int k;

	cin >> s;
	cin >> k;

	string p[5] = { "zzzzz","zzzzz","zzzzz","zzzzz","zzzzz" };

	string buf;


	for (int i = 0;i < s.size();++i) {
		for (int j = 0;j < 5 && i + j < s.size();++j) {
			buf = s.substr(i, j + 1);
			if (p[0] > buf) { 
				p[4] = p[3];
				p[3] = p[2];
				p[2] = p[1];
				p[1] = p[0];
				p[0] = buf;
				continue;
			}
			else if (p[0] == buf) {
				continue;
			}

			if (p[1] > buf) {
				p[4] = p[3];
				p[3] = p[2];
				p[2] = p[1];
				p[1] = buf;
				continue;
			}
			else if (p[1] == buf) {
				continue;
			}

			if (p[2] > buf) {
				p[4] = p[3];
				p[3] = p[2];
				p[2] = buf;
				continue;
			}
			else if (p[2] == buf) {
				continue;
			}

			if (p[3] > buf) {
				p[4] = p[3];
				p[3] = buf;
				continue;
			}
			else if (p[3] == buf) {
				continue;
			}

			if (p[4] > buf) {
				p[4] = buf;
			}

		}
	}
	cout << p[k - 1];
	return 0;

}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int x = sc.nextInt();
			
		// 計算
		int result = 1;
		int y = 0;
		for(int i = 0; i < n; i++){
		    y += sc.nextInt();
		    if(y > x) break;
		    result++;
		}
		
		// 出力
		System.out.println(result);
		
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<map>
#include<numeric>
using namespace std;

typedef long long ll;
#define modulo 1000000007 // 10^9 + 7
#define MAX 1000000000 // 10^9


int main() {
	string S; cin >> S;
	int N = S.size();
	ll before_B = 0;
	ll ans = 0;

	for (int i = 0; i < N; i++) {
		char c = S[0];
		S.erase(S.begin());
		if (c == 'B') {
			before_B++;
		}
		else {
			ans += before_B;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll

#include <bits/stdc++.h>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace std;
const long long N=200005, INF=2000000000000000000;
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }

int32_t main()
{
    IOS;
    int h,w;
    cin>>h>>w;
    string s[h];
    int dp[h+1][w+1];
    fill(dp, 0);
    for(int i=0;i<h;i++)
    cin>>s[i];
    dp[0][1]=1;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(s[i-1][j-1]=='#')
            dp[i][j]=0;
            else
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
        }
    }
    cout<<dp[h][w];
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

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

    int ans;
    if (S == "SUN") {
        ans = 7;
    } else if (S == "MON") {
        ans = 6;
    } else if (S == "TUE") {
        ans = 5;
    } else if (S == "WED") {
        ans = 4;
    } else if (S == "THU") {
        ans = 3;
    } else if (S == "FRI") {
        ans = 2;
    } else {
        ans = 1;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

string solve()
{
    set<int> s;
    map<int,int> ct;
    rep(i,12)
    {
        int e;
        cin >>e;
        s.insert(e);
        ++ct[e];
    }

    for(int i:s)for(int j:s)for(int k:s)
    {
        map<int,int> t(ct);

        if(t[i]>=4) t[i]-=4;
        else continue;
        if(t[j]>=4) t[j]-=4;
        else continue;
        if(t[k]>=4) t[k]-=4;
        else continue;

        return "yes";
    }

    return "no";
}


int main()
{
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 3152
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void solve() {
        int N, M;
        cin >> N >> M;

        vector<pair<ll, ll>> AB(N);
        for (int i = 0; i < N; ++i) {
            cin >> AB[i].first >> AB[i].second;
        }

        sort(all(AB), [](auto a, auto b) {
            if (a.first != b.first) {
                return a.first < b.first;
            } else {
                return a.second > b.second;
            }
        });

        priority_queue<ll> pq;
        ll ans = 0;
        int idx = 0;
        for (int i = 1; i <= M; ++i) {
            while (idx < AB.size() && AB[idx].first <= i) {
                pq.push(AB[idx].second);
                idx++;
            }

            if (!pq.empty()) {
                ll tmp = pq.top();
                pq.pop();
                ans += tmp;
            }
        }
        cout << ans << endl;


    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


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

int F[44];

int fib(int n){
	if(n==0||n==1){
		return F[n]=1;
	}
	if(F[n]!=-1){
		return F[n];
	}
	return F[n]=fib(n-1) + fib(n-2);
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<=n;i++){
		F[i]=-1;
	}
	cout<<fib(n)<<endl;
	
	return 0;
}

Measured memory_bytes: 1164
// A - 和風いろはちゃんイージー / Iroha and Haiku (ABC Edition) https://atcoder.jp/contests/abc042/tasks/abc042_a

  import io.Source

  object Main extends App {
    Source.stdin.getLines().foreach { line =>
      val Array(w1, w2, w3) = line.split(' ').map(_.toInt)
      println(solve(w1, w2, w3))
    }

    def solve(w1: Int, w2: Int, w3: Int): String = {
      if (w1 == 5 && w2 == 5 && w3 == 7 ||
        w1 == 5 && w2 == 7 && w3 == 5 ||
        w1 == 7 && w2 == 5 && w3 == 5)
        "YES"
      else
        "NO"
    }
  }


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

int main()
{
	ll a,b;
	cin>>a>>b;
	
	if(a==1||b==1){
		cout<<1<<endl;
		return 0;
	}
	
	ll x1=(a+1)/2;
	ll x2=a/2;
	
	ll y1=(b+1)/2;
	ll y2=b/2;
	
	cout<<(x1*y1)+(x2*y2)<<endl;
	
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int n,m;
    string a[55],b[55];
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    for(int i=0;i<=n-m;i++)
    {
        for(int j=0;j<=n-m;j++)
        {
            bool found=true;
            for (int k=0;k<m;k++)
            {
                for(int l=0; l<m; l++)
                {
                    if(a[i+k][j+l]!=b[k][l])
                    {
                        found=false;
                        break;
                    }
                }
                if(!found) break;
            }
            if(found)
            {
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 256
N, M = list(map(int,input().split()))
G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

def dfs(depth, node):
    global visited
    global ans
    visited[node] = 1
    if depth == N - 1:
        if sum(visited) == N:  ans += 1
        return
    for i in G[node]:
        if visited[i] == 0:
            dfs(depth + 1, i)
            visited[i] = 0
            
ans = 0
visited = [0 for _ in range(N)]
dfs(0, 0)
print(ans)

Measured memory_bytes: 68112
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  int arr[n];
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
 
  int x = arr[0];
  int ans = 1;
  for(long long int i = 1; i < n; i++) {
    if(x > arr[i]) {
      x = arr[i];
      ans++;
    }
  }  
  cout << ans;
  return 0;
}

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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

class unionfind {
	vector<int> par, size, num;

public:
	void init(int n) {
		par.resize(n);
		size.resize(n);
		num.resize(n);

		for (int i = 0; i < n; i++) {
			par[i] = i;
			size[i] = 1;
			num[i] = 0;
		}
	}

	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			++num[x];
			return ;
		}
		if (size[x] < size[y]) swap(x, y);

		par[y] = x;
		size[x] += size[y];
		num[x] += num[y];
		++num[x];
	}

	bool same(int x, int y) { return (find(x) == find(y)); }
	int get_size(int x) { return size[find(x)]; }
	int get_num(int x) { return num[find(x)]; }

} uf, uf2;

int main() {
	int n, h, w;

	cin >> n >> h >> w;
	uf.init(h + w);
	uf2.init(h + w);

	map<pii, vi> T;

	rep(i, n) {
		int r, c, x;
		cin >> r >> c >> x;
		--r; --c;
		T[mp(r, c)].pb(x);
		uf.unite(r, c + h);
	}

	vector<vi> cmp(h + w);
	rep(i, h + w) cmp[uf.find(i)].pb(i);

	vector<vector<pair<int, pii>>> vec(h + w);

	for (auto t : T) {
		vi cand = t.se;
		sort(ALL(cand));
		reverse(ALL(cand));
		while (cand.size() > 2) {
			cand.pop_back();
		}
		for (int x : cand) {
			vec[uf.find(t.fi.fi)].eb(x, t.fi);
		}
	}

	ll ans = 0;

	rep(i, h + w) if (vec[i].size()) {
		sort(ALL(vec[i]));
		reverse(ALL(vec[i]));

		ll t = 0;
		rep(j, vec[i].size()) {
			auto e = vec[i][j];
			int u = e.se.fi, v = e.se.se + h;

			int sz = uf2.get_size(u) + uf2.get_size(v);
			int ns = uf2.get_num(u) + uf2.get_num(v);

			if (uf2.same(u, v)) {
				ns = uf2.get_num(u);
				sz = uf2.get_size(u);
			}

			if (ns + 1 <= sz) {
				t += e.fi;
				uf2.unite(u, v);
			}
		}

		ans += t;

	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 31488
# C - Sum of product of pairs
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
sum1 = sum(A)
sum2 = 0
for a in A:
    sum2 += a**2
ans = (sum1**2-sum2)//2
ans %= MOD
print(ans)

Measured memory_bytes: 94264
n = int(raw_input())
l = [[0,False]]
for _ in range(n):
    l.append([int(raw_input()), False])
l[1][1] = True
p = 1
while True:
    p = l[p][0]
    if l[p][1] == True:
        break
    l[p][1] = True
    if p == 2:
        break
if l[2][1] == True:
    c = 0
    for [_,f] in l:
        if f == True:
            c += 1
    print c - 1
else:
    print -1


Measured memory_bytes: 19076
import java.util.Scanner;

public class Main {

	public static void main(final String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int D = sc.nextInt();
		int x = sc.nextInt();
		sc.close();
		for(int i = 1; i <= 10; i++) {
			x = (r * x) - D;
			System.out.println(x);
		}
	}
}

Measured memory_bytes: 21716
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    string s;
    long long int k;
    cin >> s >> k;
    bool flag = true;
    char c = s[0];
    for(int i = 1;i < s.size();i++)
    {
        if(c != s[i])
        {
            flag = false;
            break;
        }
    }
    if(flag)
    {
        long long int s_size = s.size();
        cout << s_size * k / 2 << "\n";
        return 0;
    }
    long long int a = 0;
    for(int i = 1;i < s.size();i++)
    {
        long long int count = 1;
        while(s[i] == s[i - 1])
        {
            count++;
            i++;
        }
        if(count > 1)
        {
            a += count / 2;
        }
    }
    if(s[0] != s[s.size() - 1])
    {
        cout << a * k << "\n";
    }
    else
    {
        s += s;
        long long int b = 0;
        for(int i = 1;i < s.size();i++)
        {
            long long int count = 1;
            while(s[i] == s[i - 1])
            {
                count++;
                i++;
            }
            if(count > 1)
            {
                b += count / 2;
            }
        }
        cout << a + (b - a) * (k - 1) << "\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
a,b = map(str,input().split())
a = int(a)
if len(b) == 4:
    b = int(b[0] + b[2:])
    
else:
    b = int(b[0] + b[2] +'0')
tmp = str(a*b)
if len(tmp) <=2:
    print(0)
else:
    tmp = str(a*b)[:-2]
    print(int(tmp))

Measured memory_bytes: 9196
D,G = map(int, input().split())

#prob_num = [3,5]
#comp = [500,800]

prob_num = []
comp = []

for i in range(D):
    p,c = map(int, input().split())
    prob_num.append(p)
    comp.append(c)

comp_point = []
for i in range(D):
    comp_point.append((100*(i+1)*prob_num[i]+comp[i]))



ans = 1000000
for b in range(1<<D):
    hasComp = []
    for j in range(D):
        if b & (1<<j):
            hasComp.append(True)
        else:
            hasComp.append(False)
        
    # compしてるものを決め打ち
    point = 0
    prb = 0
    for i in range(D):
        if hasComp[i]:
            point += comp_point[i]
            prb += prob_num[i]
    
    res = G-point
    
    while res>0:
        flag = 0
        for i in range(D-1,-1,-1):
            if not hasComp[i]:
                if res <= (100*(i+1)*(prob_num[i]-1)):
                    req_prob = (res//(100*(i+1))) + bool(res%(100*(i+1)))
                    prb += req_prob
                    res = 0
                    break
                
                else:
                    prb += (prob_num[i]-1)
                    res -= (100*(i+1))*(prob_num[i]-1)
        
            if i==0:
                flag = 1
                break
        
        if flag:
            break
    if res<=0:
        ans = min(ans,prb)
    
print(ans)
             

Measured memory_bytes: 3064
import sys
msg = str(input())

# 逆から、大きい文字数から、見ていけば重複は生じない
len_l1 = 0
while len(msg) != len_l1:
    len_l1 = len(msg)
    
    # dreamer
    if msg[-7:] == "dreamer":
        msg = msg[:-7]
    # eraser
    if msg[-6:] == "eraser":
        msg = msg[:-6]
        
    # dreame
    if msg[-5:] == "dream":
        msg = msg[:-5]
    # erase
    if msg[-5:] == "erase":
        msg = msg[:-5]
        
    if len(msg) == 0:
        print('YES')
        sys.exit()    
    
print('NO')

Measured memory_bytes: 3268
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[2001][2001];
int main(void){
	ll n,i,j,a[2001],temp,x,y,z,t,r,mx;
	cin>>n;
	for(i=0;i<n;i++) cin>>a[i];
	for(i=0;i<=n;i++) for(j=0;j<=n;j++) dp[i][j]=-1;
	for(i=0;i<n;i++) dp[0][i]=a[i];
	for(i=0;i<n-1;i++){
		for(j=0;j<n;j++){
			if(dp[i][j]!=-1){
				z=j;
				x=z-1; y=z+i+1;
				if(x<0) x=n-1;
				if(y>=n) y=y-n;
				if(i%2==1){
					r=a[x]; t=a[y];
					if(dp[i+1][x]<dp[i][j]+r) dp[i+1][x]=dp[i][j]+r;
					if(dp[i+1][z]<dp[i][j]+t) dp[i+1][z]=dp[i][j]+t;
				}
				else {
					if(a[x]>a[y]){
						if(dp[i+1][x]<dp[i][j]) dp[i+1][x]=dp[i][j];
					}
					else {
						if(dp[i+1][z]<dp[i][j]) dp[i+1][z]=dp[i][j];
					}
				}
			}
		}
	}
/*	for(i=0;i<n;i++){
		for(j=0;j<n;j++) cout<<dp[i][j]<<' ';
		cout<<endl;
	}*/
	mx=LLONG_MIN;
	for(i=0;i<n;i++) mx=max(mx,dp[n-1][i]);
	cout<<mx<<endl;
	return 0;
}


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

int main(){

    int N;
    cin >> N;

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

    int ans = 0;

    for(int i=1;i<N-1;i++){
        if((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i+1] < p[i] && p[i] < p[i-1])){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256