akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

void print() { cout << endl; }
template <typename Head, typename... Tail>
void print(Head head, Tail... tail) {
    int size = sizeof...(Tail);
    cout << head;
    if (size > 0) {
        cout << " ";
    }
    print(tail...);
}

void print0() {}
template <typename Head, typename... Tail>
void print0(Head head, Tail... tail) {
    cout << head;
    print0(tail...);
}

struct edge {
    ll u;
    ll v;
    ll cost;
};
bool operator<=(const edge& lhs, const edge& rhs) {
    return lhs.cost <= rhs.cost;
}
bool operator<(const edge& lhs, const edge& rhs) {
    return lhs.cost < rhs.cost;
}
bool operator>=(const edge& lhs, const edge& rhs) {
    return lhs.cost >= rhs.cost;
}
bool operator>(const edge& lhs, const edge& rhs) {
    return lhs.cost > rhs.cost;
}
bool operator==(const edge& lhs, const edge& rhs) {
    return lhs.cost == rhs.cost;
}
bool operator!=(const edge& lhs, const edge& rhs) {
    return lhs.cost != rhs.cost;
}

void dijkstra(ll start, vector<vector<edge>>& edgemap, vector<ll>& min_cost) {
    vector<bool> done(edgemap.size(), false);
    priority_queue<edge, vector<edge>, greater<edge>> pq;

    pq.push(edge{u : -1, v : start, cost : 0});
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (done[e.v]) {
            continue;
        }
        done[e.v] = true;
        min_cost[e.v] = e.cost;
        for (auto next_e : edgemap[e.v]) {
            if (!done[next_e.v]) {
                edge total_next_e = next_e;
                total_next_e.cost = e.cost + next_e.cost;
                pq.push(total_next_e);
            }
        }
    }
}

// dijkstra (ダイクストラ)
// https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d
int main() {
    ll n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<edge> edges;
    vector<vector<edge>> edgemap_yen(n + 1);
    vector<vector<edge>> edgemap_snuuk(n + 1);
    for (ll j = 0; j < m; j++) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        edgemap_yen[u].push_back(edge{u : u, v : v, cost : a});
        edgemap_yen[v].push_back(edge{u : v, v : u, cost : a});
        edgemap_snuuk[u].push_back(edge{u : u, v : v, cost : b});
        edgemap_snuuk[v].push_back(edge{u : v, v : u, cost : b});
    }
    ll INF = 9e18;
    vector<ll> min_yen(n + 1, INF);
    vector<ll> min_snuuk(n + 1, INF);
    dijkstra(s, edgemap_yen, min_yen);
    dijkstra(t, edgemap_snuuk, min_snuuk);

    ll init_yen = (ll)1e15;
    vector<pair<ll, ll>> last_snuuk(n + 1);
    for (int i = 1; i <= n; i++) {
        last_snuuk[i] = make_pair(i, init_yen - min_yen[i] - min_snuuk[i]);
    }
    last_snuuk[0] = make_pair(0, -1);

    sort(last_snuuk.begin(), last_snuuk.end(), [](pair<ll, ll> p, pair<ll, ll> q) { return p.second > q.second; });

    ll year = 0;
    ll city = 0;
    vector<ll> result(n);
    while (year < n) {
        if (last_snuuk[city].first > year) {
            result[year] = last_snuuk[city].second;
            year++;
        } else {
            city++;
        }
    }

    for (auto r : result) {
        cout << r << endl;
    }
}


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

int main() {
  string str1, str2;
  int count = 0;
  cin >> str1;
  cin >> str2;
  for(int i=0;i<str1.length();i++) {
    if(str1[i] != str2[i]) {
      count++;
    }
  }
  cout << count;
}




Measured memory_bytes: 3848
#include <iostream>
using namespace std;
int main(void)
{
    int d;
    cin >> d;
    if (d == 25)
    {
        cout << "Christmas" << endl;
    }
    else if (d == 24)
    {
        cout << "Christmas Eve" << endl;
    }
    else if (d == 23)
    {
        cout << "Christmas Eve Eve" << endl;
    }
    else if (d == 22)
    {
        cout << "Christmas Eve Eve Eve" << endl;
    }
}

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

int main() {
  	vector<long> a(5);
  	for(long i = 0; i< 5; i++){
      cin >> a[i];
    }
    for(long i = 0; i< 5; i++){
      if(a[i]==0){
        cout << i+1 << endl;
        break;
      }
    }
}

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

using ll = long long int;

bool used[10];
string s, ans;
ll maxi, diff = 0;

void rec(int n, string t){
    // cout << n << " " << t << endl;
    if(n == 0){
        ll d = abs(stol(s)-stol(t));
        if(min(d, maxi-d) > diff){
            ans = t;
            diff = min(d, maxi-d);
        }else if(min(d, maxi-d) == diff && stol(ans)>stol(t)){
            ans = t;
        }
        return;
    }
    for(int i=0;i<10;i++){
        if(!used[i]){
            t.push_back('0'+i);
            used[i] = true;
            rec(n-1,t);
            t.pop_back();
            used[i] = false;
        }
    }
}

int solve(){
    cin >> s;
    maxi = ll(pow(10,s.size()));
    rec(s.size(), "");
    cout << ans << endl;
    return 0;
}

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



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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

struct edge {
    ll to, cost;
    edge(ll a, ll b) {
        to = a;
        cost = b;
    }
};

// distance,number
using P = pair<ll, ll>;

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<edge>> g(n);
    ll zero_memo[n] = {};
    rep(i, m) {
        ll l, r, c;
        cin >> l >> r >> c;
        l--;
        r--;
        g[l].push_back(edge(r, c));
        zero_memo[l]++;
        zero_memo[r]--;
    }

    ll sum = 0;
    rep(i, n - 1) {
        sum += zero_memo[i];
        if (sum > 0) {
            g[i + 1].push_back(edge(i, 0));
        }
    }

    ll d[n];
    fill(d, d + n, mod * mod);
    priority_queue<P, vector<P>, greater<P>> q;
    d[0] = 0;
    q.push(P(0, 0));
    while (!q.empty()) {
        P p = q.top();
        q.pop();
        ll v = p.second;
        if (d[v] < p.first)
            continue;
        rep(i, g[v].size()) {
            edge e = g[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(P(d[e.to], e.to));
            }
        }
    }

    if (d[n - 1] == mod * mod) {
        cout << -1 << endl;
        return 0;
    }
    cout << d[n - 1] << endl;

    return 0;
}



Measured memory_bytes: 12868
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
  int i, c;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p == NIL) printf("root, ");
  else if(T[u].l == NIL) printf("leaf, ");
  else printf("internal node, ");
  
  printf("[");
  for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");
  
}

void calcDepth(int u, int p){
  D[u] = p;
  if(T[u].l != NIL) calcDepth(T[u].l,p+1);
  if(T[u].r != NIL) calcDepth(T[u].r,p);
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;
  
  for(i=0; i<n; i++){
    scanf("%d %d", &id, &k);
    for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
      sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);

  //出力 (output)
  for(i=0; i<n; i++) print(i);
  
  return 0;
}



Measured memory_bytes: 3344
#include "bits/stdc++.h"
using namespace std;
typedef long long int lli;
#define pb push_back



int main() {
	int n,k;
	cin >> n >> k;
	vector<int > ar(n);

	for (int i = 0; i < n; ++i)
	{
		/* code */
		cin >> ar[i];
	}

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

	int sum = 0;
	for (int i = 0; i < k; ++i)
	{
		/* code */
		sum  = sum + ar[i];
	}

	cout << sum << endl;

}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
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; }

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<ll>a(n);
  rep(i, 0, n)cin >> a[i];
  sort(a.begin(),a.end(),greater<ll>());
  ll ans = a[0];
  int cnt = 1;
  if(n==2){
      cout << a[0] << endl;
      return 0;
  }
  rep(i, 1, n){
      ans += a[i];
      cnt++;
      if(cnt==n-1){
          cout << ans << endl;
          return 0;
      }
      ans += a[i];
      cnt++;
      if(cnt==n-1){
          cout << ans << endl;
          return 0;
      }
  }
}

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

public class Main {
	public static void main(String[] args) throws IOException{
		final BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int[][] x=new int[1001][1001];
		for(int i=0;i<n;i++){
			int line = 0;
			String str1=br.readLine();
			String str2=br.readLine();
			
			for(int j=1;j<=str1.length();j++){
				for(int k=1;k<=str2.length();k++){
					char a=str1.charAt(j-1);
					char b=str2.charAt(k-1);
					if(a==b) x[j][k]=x[j-1][k-1]+1;
					else x[j][k]=Math.max(x[j-1][k],x[j][k-1] );
					line=Math.max(line, x[j][k]);
				}
				
			}
			System.out.println(line);
		}
		br.close();
	}
}

Measured memory_bytes: 26144
import numpy as np


N = int(input())
A, B = map(int, input().split(" "))
P_list = np.array(list(map(int, input().split(" "))))

min_A = P_list[P_list <= A]
min_B = P_list[(P_list > A) & (P_list <= B)]
above_B = P_list[P_list > B]

print(min(len(min_A), len(min_B), len(above_B)))


Measured memory_bytes: 21652
#include "bits/stdc++.h"
using namespace std;

#define ll long long int
#define loop(i,s,e) for(ll i=s; i<e; i++)
#define endl '\n'
#define vll vector<ll>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define N 100001
#define pb push_back
#define INF LLONG_MAX
#define inf INT_MAX
#define minusinf INT_MIN

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

ll n, w;
ll weight[101], value[101];
ll dp[101][100001];

ll util(ll i, ll wt){
	if(i>=n) return 0;

	if(dp[i][wt]!=-1) return dp[i][wt];

	ll a = minusinf, b = minusinf;

	if(wt + weight[i] <= w) a = value[i] + util(i+1, wt + weight[i]);
	b = util(i+1, wt);

	return dp[i][wt] = max(a, b);
}

void alpha(){

	cin>>n>>w;
	loop(i,0,n) cin>>weight[i]>>value[i];

	memset(dp, -1, sizeof(dp));

	cout<<util(0, 0)<<endl;

	return;

}

int main(){

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

    ll t=1;
	//cin>>t;

  	while(t--) alpha();

	return 0;

}

Measured memory_bytes: 79232
#include <stdio.h>

void digit_scan(int a, int b)
{
  int i, sum;
  i = 1;

  sum = a + b;

  while((sum /= 10) != 0) 
    i++;

  printf("%d\n", i);
}
int main(int argc, char *argv[])
{
  int a, b;

  while((scanf("%d %d", &a, &b)) != EOF)
    digit_scan(a, b);

  return 0;
}

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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

int main(){
    cout << setprecision(20);
    ll n, k;
    cin >> n >> k;
    vll a(n);
    rep(i, n) cin >> a[i];

    vll s(n+1, 0);
    ll t = 0;
    s[0] = 0;
    rep(i, n){
        s[i+1] = a[i] + t;
        t = s[i+1];
    }
    rep(i, n+1){
        s[i] -= i;
        s[i] %= k;
        s[i] = (s[i]+k) % k;
    }
    map<ll, ll> m;
    ll count = 0;
    deque<ll> q;
    rep(i, n+1){
        if(m.find(s[i]%k)!=m.end()){
            count += m[s[i]%k];
        }
        if(m.find(s[i]%k)!=m.end()) ++m[s[i]%k];
        else m.insert({s[i]%k, 1});
        q.push_back(s[i]%k);
        if(q.size()>=k){
            ll e = q.front();
            q.pop_front();
            --m[e];
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 17536
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
    static long memo[][];
    static int w[];
    static int v[];
    static int n;
   public static void main(String args[])
   {
       Scanner sc=new Scanner(System.in);
       n=sc.nextInt();
       int W=sc.nextInt();
       w=new int[n];
       v=new int[n];
       for(int i=0;i<n;i++)
       {
           w[i]=sc.nextInt();
           v[i]=sc.nextInt();
       }
       memo=new long[n][W+1];
       for(int i=0;i<n;i++)Arrays.fill(memo[i],-1);
       long ans=solve(0,W);
       System.out.println(ans);
       
   }
   public static long solve(int i,int W)
   {
       if(W<0)return Long.MIN_VALUE;
       if(i==n)return 0;
       if(W==0)return 0;
       
       if(memo[i][W]!=-1)return memo[i][W];
       return memo[i][W]=Math.max(solve(i+1,W),solve(i+1,W-w[i])+v[i]);
   }
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x, y;
	cin >> x >> y;
	int cnt = 0;
	while (x <= y) {
		cnt++;
		x *= 2;
	}
	cout << cnt << endl;
}


Measured memory_bytes: 764
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, k;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> k;
  vector<int> v;

  REP(i, n) {
    int h;
    cin >> h;

    v.push_back(h);
  }

  sort(v.begin(), v.end(), greater<int>());

  ll ans = 0;
  REP(i, n) {
    if(i >=  k) ans += v[i];
  }

  cout << ans << endl;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  srand((unsigned)time(NULL));
  ll N;
  cin >> N;
  vll A(N);
  vll counter(100001, 0);
  vll num(100001);
  for(ll i = 1; i <= 100000; i++){
    num.at(i) = i;
  }
  ll sum = 0;
  for(ll i = 0; i < N; i++){
    cin >> A.at(i);
    sum += A.at(i);
    counter.at(A.at(i))++;
  }
  ll Q;
  cin >> Q;
  while(Q--){
    ll B, C;
    cin >> B >> C;
    sum -= counter.at(B) * B;
    sum += counter.at(B) * C;
    counter.at(C) += counter.at(B);
    counter.at(B) = 0;
    cout << sum << endl;
  }
}


Measured memory_bytes: 5564
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a;
        String op;
        int b;
        int c;
        while (true) {
             a = sc.nextInt();
             op = sc.next();
             b = sc.nextInt();

            if (op.equals("?")){
                break;}
            if (op.equals("+")){
                c = a + b;
                System.out.println(c);}
            else if (op.equals("-")){
                c = a - b;
            System.out.println(c);}
            else if (op.equals("*")){
                c = a * b;
            System.out.println(c);}
            else{
            c = a / b;
            System.out.println(c);}
        }
    }
}


Measured memory_bytes: 26260
N = int(input())
A = [list(input().split()) for _ in range(N)]

cont_M = 0
cont_A = 0
cont_R = 0
cont_C = 0
cont_H = 0

for i in range(N):
    if A[i][0][0] =='M':
        cont_M += 1
    elif A[i][0][0] =='A':   
        cont_A += 1
    elif A[i][0][0] =='R':   
        cont_R += 1
    elif A[i][0][0] =='C': 
        cont_C += 1
    elif A[i][0][0] =='H': 
        cont_H += 1
B = [cont_M , cont_A , cont_R , cont_C , cont_H ]

#Mで始まる人の人数 x Aで始まる人の人数 x Rで始まる人の人数 これを全ての仮定パターン（5C3の通り)の組み合わせの和を求める。

import itertools

c = list(itertools.combinations(B, 3))

ans = 0
for i in c:
    ans += i[0] * i[1] * i[2]
    
print(ans)


Measured memory_bytes: 20716
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;

using namespace std;

int main()
{
    ll L, R, t;    cin >> L >> R;
    vector<int> check(2019,0);
    for(ll i=L; i<R; i++){
        for(ll j=i+1; j<=R; j++){
            t = i*j%2019;
            check[t] = 1;
            if(t == 0){
                cout << 0;
                return 0;
            }
        }
    }
    rep(i,2019){
        if(check[i] == 1){
            cout << i;
            return 0;
        }
    }
}

Measured memory_bytes: 3544
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// 大文字と小文字の入れ替え
func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	s := sc.Text()
	sr := ""
	for _, x := range s {
		xs := string(x)
		u := strings.ToUpper(xs)
		l := strings.ToLower(xs)
		if u == xs {
			sr += l
		} else if l == xs {
			sr += u
		} else {
			sr += xs
		}
	}
	fmt.Println(sr)
}



Measured memory_bytes: 1808
/*Read the problem carefully before starting to work on it*/
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}

#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007

double PI=3.1415926535897932384626;

//template<typename T> T power(T x,T y,ll m=mod){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

#define fi first
#define se second

ll dp[100005];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll n;
    cin>>n;
    vector<ll>arr(n);
    for(ll i=n-1;i>=0;i--)
    {
        cin>>arr[i];
    }
    dp[0]=1;
    ll ans=1;
    for(ll i=1;i<n;i++)
    {
        if(arr[i]>=arr[i-1])
        {
            dp[i]=dp[i-1]+1;
        }
        else
        {
            dp[i]=1;
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans-1;
    return 0;
}


//252908XL

Measured memory_bytes: 1792
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#pragma region Macros
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define all(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
int gcd(int a, int b) // assuming a,b >= 1
{
    if (a < b)
        swap(a, b);
    if (b == 0)
        return a;
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}
int lcm(int a, int b) // assuming a,b >= 1
{
    return  a * b / gcd(a, b);
}
using namespace std;
#pragma endregion
signed main() {
    int N;
    string S;
    cin >> S;
    N = S.size();
    rep(i, N) {
        if (i%2 == 0 && S[i] == 'L') {
            cout << "No";
            return 0;
        }
        if (i%2 == 1 && S[i] == 'R') {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[4]={0,1,0,-1},mdy[4]={-1,0,1,0};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int w,h;
char c[25][25];
int starty,startx;
vector<Pi> dirty;
int dis[11][11];
int inv[25][25];
vector<int> aa;

int main(){
	while(1){
		cin>>w>>h;
		if(w==0&&h==0)break;
		int flag=1;
		REP(i,11)
			REP(j,11)
				dis[i][j]=0;
		dirty.clear();
		REP(i,h)
			REP(j,w){
				cin>>c[i][j];
				if(c[i][j]=='o'){
					starty=i;
					startx=j;
					dirty.push_back(Pi(i,j));
				}
			}
		REP(i,h)
			REP(j,w){
				if(c[i][j]=='*'){
					dirty.push_back(Pi(i,j));
				}
			}
		queue<Pi> qq;
		for(int i=0;i<dirty.size();i++){
			REP(k,25)
				REP(j,25)
					inv[k][j]=-1;
			qq.push(dirty[i]);
			inv[dirty[i].first][dirty[i].second]=0;
			while(qq.size()){
				Pi q1=qq.front();qq.pop();
				for(int j=0;j<4;j++){
					int ny=q1.first+dy[j];
					int nx=q1.second+dx[j];
					if(0<=nx&&nx<w&&0<=ny&&ny<h&&inv[ny][nx]==-1&&c[ny][nx]!='x'){
						inv[ny][nx]=inv[q1.first][q1.second]+1;
						qq.push(Pi(ny,nx));
					}
				}
			}
			/*REP(j,h){
				REP(i,w){
					cout<<inv[j][i]<<" ";
				}
				cout<<endl;
			}
			cout<<endl;*/
			for(int j=0;j<dirty.size();j++){
				
				dis[i][j]=inv[dirty[j].first][dirty[j].second];
				//printf("%3d",dis[i][j]);
				if(dis[i][j]==-1)flag=0;
			}
			//printf("\n");
		}
		
		/*REP(i,dirty.size()){
			REP(j,dirty.size()){
				cout<<dis[i][j]<<" ";
			}
			cout<<endl;
		}*/
		vector<int> vv;
		vv.clear();
		for(int i=1;i<dirty.size();i++){
			vv.push_back(i);
		}
		if(flag==0){
			aa.push_back(-1);
			continue;
		}
		int ans=1e8;
		do{
			int tans=0;
			tans+=dis[0][vv[0]];
			for(int i=0;i<vv.size()-1;i++){
				tans+=dis[vv[i]][vv[i+1]];
			}
			ans=min(tans,ans);
			//cout<<vv[0]<<" "<<vv[1]<<" "<<vv[2]<<endl;
		}while(next_permutation(vv.begin(),vv.end()));
		aa.push_back(ans);
	}
	REP(i,aa.size())cout<<aa[i]<<endl;
	return 0;
}


Measured memory_bytes: 3180
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second 
#define mp make_pair
#define int long long
int arr[100005],dp[100005];
signed main()
{
    IOS
    int n,k; cin>>n>>k;
    int temp,dick;
    for(int i=1;i<=n;i++) cin>>arr[i];
    dp[1] = 0;
    dp[2] = fabs(arr[2] - arr[1]);
    for(int i = 3;i <= n;i++)
    {
      temp = 100000000000;
      for(int j = max(1LL,i-k);j<i;j++)
      {
        dick = fabs(arr[i]-arr[j]);
        temp = min(temp , dp[j] + dick);
      }
      dp[i] = temp;
    }
    cout<<dp[n]<<endl;
    return 0;
}

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

int main() {
    int n; cin >> n;
    long long x = 0;
    for (int i = 0; i < n; i++) {
        long long h; cin >> h;
        if (x < h) x = h;
        if (x > h + 1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input()
jdg = False

if (n % 2 == 0):
    for i in range(n // 2):
        if (s[i] != s[i + n // 2]):
            break
        if (i == n // 2 - 1):
            jdg = True
print('Yes' if jdg else 'No')


Measured memory_bytes: 2940
#include <cstdio>
#include <cstdint>
#include <cstddef>
#include <vector>

template <class RandomIt>
intmax_t tsurai(RandomIt first, RandomIt last) {
  ptrdiff_t len=last-first;
  if (len == 1) {
    return 0;
  } else if (first[1] > 1) {
    return -1;
  }

  for (RandomIt it=first; it<last; ++it)
    if (*it > it-first)
      return -1;

  intmax_t lastx=0, res=0;
  for (RandomIt it=first+1; it<last; ++it) {
    if (*it == 1 || *it == lastx+1) {
      ++res;
    } else if (*it <= lastx) {
      res += *it;
    } else {
      return -1;
    }
    lastx = *it;
  }
  // fprintf(stderr, "%jd\n", res);
  return res;
}

int main() {
  size_t N;
  scanf("%zu", &N);
  std::vector<int> A(N+1);
  for (size_t i=0; i<N; ++i)
    scanf("%d", &A[i]);

  if (A[0] != 0)
    return !printf("-1\n");

  intmax_t res=0;
  auto first=A.begin();
  for (auto it=A.begin()+1; it<A.end(); ++it) {
    if (*it == 0) {
      intmax_t cur=tsurai(first, it);
      if (cur < 0)
        return !printf("-1\n");

      res += cur;
      first = it;
    }
  }
  printf("%jd\n", res);
}


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

int main() {
  int K, S;
  cin >> K >> S;
 
  int count = 0;
  for (int i = 0; i <= K; i++) {
    for (int j = 0; j <= K; j++) {
      if ((S-i-j <= K) && (S-i-j >= 0))
       count ++;
    }
  }  
   cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF (1<<30)

int main(){
  int maxx,n;
  int data[260];
  bool d[260][260];
  while(cin >> maxx,maxx){
    cin >> n;
    int N = n + 2;
    memset(d,false,sizeof(d));
    memset(data,0,sizeof(data));
    for(int i=0;i<n;i++){
      cin >> data[i+1];
    }
    for(int i=0;i<N;i++){
      for(int j=1;j<=maxx && i+j<N;j++){
	if(j+i == n+1) d[i][n+1] = true;
	else {
	  if(j+i+data[j+i] >= n+1) d[i][n+1] = true;
	  else if(j+i+data[j+i] < 0) d[i][0] = true;
	  else d[i][i+j+data[j+i]] = true;
	}
      }
    }
    for(int k=0;k < N;k++){
      for(int i=0;i < N;i++){
	if(d[i][k] == false) continue;
	for(int j=0;j < N;j++){
	  if(d[k][j] == false) continue;
	  d[i][j] = true;
	}
      }
    }
    bool flag = false;
    for(int i=0;i<=n;i++){
      if(d[0][i] && (!d[i][n+1])){
	flag = true;
	cout << "NG" << endl;
	break;
      }
    }
    if(!flag) cout << "OK" << endl;
  }
}

Measured memory_bytes: 1232
#include<iostream>
#include<string>
using namespace std;
int main(void) {
  string s;
  cin>>s;
  if((s[0]==s[1] and s[1]==s[2]) or (s[1]==s[2] and s[2]==s[3]))
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = defaultdict(lambda :-INF)
dp[(0,0,0)] = 0

for i in range(1, N+1):
    for j in range(i//2-1, i//2+2):
        dp[1,i,j] = dp[0,i-1,j-1]+A[i-1]
        dp[0,i,j] = max(dp[1,i-1,j], dp[0,i-1,j])

ans = max(dp[1,N,N//2], dp[0,N,N//2])
print(ans)


Measured memory_bytes: 371784
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

// int min(int a, )

int main(){
    int k,n;
    string s;
    cin >> n >> k;
    cin >> s;

    vector<int> renzoku;

    int count = 1;
    int now = 1;
    int i;
    for(i=1;i<n;i++){
        if(s[i]==(char)('0'+now)){
            count++;
        }else{
            renzoku.push_back(count);
            count=1;
            now = 1-now;
        }
    }
    if(count!=0){
        renzoku.push_back(count);
    }
    if(renzoku.size() % 2 == 0){
        renzoku.push_back(0);
    }

    // rep(i, renzoku.size()){
    //     cout << renzoku[i] << ' ';
    // }
    // cout << endl;

    int width = 2*k+1;
    int ans = 0;
    int leftpointer = 0;
    int rightpointer = 0;
    int tmp = 0;
    for (int i = 0; i < renzoku.size(); i += 2){
        int left = i;
        int right = min(i + width, (int)renzoku.size());
        while(left > leftpointer){
            tmp -= renzoku[leftpointer];
            leftpointer++;
        }
        while(right > rightpointer){
            tmp += renzoku[rightpointer];
            rightpointer++;
        }
        ans = max(tmp,ans);

    }
    cout << ans << endl;

    return 0;
}

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

#define MAX_N 60000

long long N;

/*
 *エラトステネスの篩
 *多くの整数を素数判定したい場合には、より効率的な 方法があります。
 */
int prime[MAX_N]; // i番目の素数
bool is_prime[MAX_N + 1]; // is_prime[i]がtrueならiは素数
// n以下の素数の数を返す
int sieve(int n) {
	int p = 0;
	for (int i = 0; i <= n; i++){
		is_prime[i] = true;
	}
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			prime[p++] = i;
			for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
		}
	}
	return p;
}

int main(){
	vector<long long> vec;
	cin >> N;
	sieve(55555);
	for(long long i = 0; i <= 55555; i++){
		if(i%5 == 1 && is_prime[i]){
			vec.push_back(i);
		}
	}

	for(long long i = 0; i < N; i++){
		cout << vec[i];
		if(i != N-1){
			cout << " ";
		}
	}
	cout << endl;
}

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

ll dp[(ll)1e5 + 5][13];

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

    string str;
    cin >> str;

    int N = 13;
    int size = str.size();

    int digit = 1;
    dp[0][0] = 1; // 0桁目を13で割った余りが0の個数は1

    for (int i = size - 1; i >= 0; i--) {
	char c = str[i];
	if (c == '?') {
	    for (int k = 0; k < 10; k++) { // '？'が取りうる値
		for (int j = 0; j < N; j++) { // 前回桁の余り
		    int tmp = (k * digit + j) % N;
		    dp[size - i][tmp] += dp[size - i - 1][j];
		    dp[size - i][tmp] %= INF;
		}
	    }

	} else {
	    int k = (int)(str[i] - '0');
	    for (int j = 0; j < N; j++) {
		int tmp = (k * digit + j) % N;
		dp[size - i][tmp] += dp[size - i - 1][j];
		dp[size - i][tmp] %= INF;
	    }
	}
	digit *= 10;
	digit %= N;
    }

    cout << dp[size][5] << endl;
    return 0;
}


Measured memory_bytes: 10704
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();
    
    int m, f, b;
    cin >> m >> f >> b;
    if (m >= b)cout << "0\n";
    else if (m + f >= b)cout << b - m << "\n";
    else cout << "NA\n";
}


Measured memory_bytes: 3236
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define O 0
#define I 1

int n,D[N][N],color[N],d[N],f[N],m;

void idfs(int);
void dfs(void);

int main(){
  int i,j,u,v,k;
  scanf("%d",&n);
  for(i=O;i<n;i++){
    for(j=O;j<n;j++){
      D[i][j]=O;
    }
  }
  for(i=O;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=O;j<k;j++){
      scanf("%d",&v);
      D[u-I][v-I]=I;
    }
  }
  dfs();
  return O;
}

void idfs(int u){
  int v;
  color[u]=GRAY;
  d[u]=++m;
  for(v=O;v<n;v++){
    if(D[u][v]==O)
      continue;
    if(color[v]==WHITE){
      idfs(v);
    }
  }
  color[u]=BLACK;
  f[u]=++m;
}

void dfs(){
  int i;
  for(i=O;i<n;i++){
    color[i]=WHITE;
  }
  m=O;
  for(i=O;i<n;i++){
    if(color[i]==WHITE){
      idfs(i);
    }
  }
  for(i=O;i<n;i++){
    printf("%d %d %d\n",i+I,d[i],f[i]);
  }
}



Measured memory_bytes: 2112
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <bitset>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)

using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

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

    ll i,j,h;
    ll Q,M,K,P,A,B,C,N,X;

    long double x;

    string S,T;

    ll ans=0;
    ll count=0;
    ll flag=0;
    ll temp=0;

    vector<ll> aa, bb, hh, ff;

    cin >>A>>B>>C>>K;


    if(K<=A){ans=K;}
    else if(K>A && K<=A+B){
        ans=A;
    }else{
        ans=A-(K-A-B);
    }



    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (ll i=0; i<(n); ++i)
#define rep1(i,n) for (ll i=1; i<=(n); ++i)
typedef long long ll;
bool debug=false;
string yes = "Yes";
string no = "No";

int main(){
  ll n; cin >> n;
  ll ans=0;
  for(ll p=1;p*p<n; p++){
    if(n%p!=0) continue;
    ll m = n/p -1;
    if(m>p) ans+=m;
  }
  printf("%lld",ans);
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <numeric>
#include <iostream>

using namespace std;

#define FOR(i, a, b)   for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b)  for(int i = (a); i > (b); --i)
#define rep(i, n)      for(int i = 0; i < (n); ++i)
#define all(c)         begin(c), end(c)
#define rall(c)        rbegin(c), rend(c)
#define SZ(a)          ((ll) a.size())

typedef long long ll;
typedef unsigned long long ull;

int main() {
	int N;
	cin >> N;
	vector<ll> a(N);
	rep(i, N) scanf("%d", &a[i]);
	int ans = 0;
	rep(i, N) {
		while (1) {
			if (a[i] % 2 == 0) {
				a[i] = a[i] / 2;
				ans++;
			}
			else break;
		}
	}
	cout << ans;
	return 0;
}

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

int main() {
  int N;
  cin>>N;
  int sum=0;
  rep(i,N){
    int a;
    cin>>a;
    sum += a;
  }
  cout<<sum-N<<endl; 
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5050,M=220,oo=1000000001;
int i,j,k,n,m,ch;
int A[N],B[N][M],l[N],r[N];
ll ans,f[N][N],s[N];
void R(int &x) {
	x=0;ch=getchar();
	while (ch<'0' || '9'<ch) ch=getchar();
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
}
void W(ll x) {
	if (x>=10) W(x/10);
	putchar(x%10+'0');
}
void Add(int x1,int y1,int x2,int y2,int x) {
	f[x1][y1]+=x;
	f[x1][y2+1]-=x;
	f[x2+1][y1]-=x;
	f[x2+1][y2+1]+=x;
}
int main() {
	R(n);R(m);
	for (i=1;i<n;i++) R(A[i]);
	for (i=1;i<n;i++) s[i]=s[i-1]+A[i];
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++) R(B[i][j]);
	for (j=1;j<=m;j++) {
		B[0][j]=B[n+1][j]=oo;
		for (i=1;i<=n;i++) {
			l[i]=i-1;
			while (B[l[i]][j]<B[i][j]) l[i]=l[l[i]];
		}
		for (i=n;i;i--) {
			r[i]=i+1;
			while (B[r[i]][j]<=B[i][j]) r[i]=r[r[i]];
		}
		for (i=1;i<=n;i++) Add(l[i]+1,i,i,r[i]-1,B[i][j]);
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++) {
			f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
			if (i<=j) ans=max(ans,f[i][j]-(s[j-1]-s[i-1]));
		}
	W(ans);puts("");
}

Measured memory_bytes: 203776
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

double dp[3010][3010];

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

    int n;
    cin >> n;
    vector<double> p(n);
    rep(i, n) cin >> p[i];
    dp[0][0] = 1;
    rep(i, n) rep(j, n + 1)
    {
        dp[i + 1][j] = dp[i][j] * (1 - p[i]);
        if (j > 0)
            dp[i + 1][j] += dp[i][j - 1] * p[i];
    }
    double ans = 0;
    for (int i = (n + 1) / 2; i <= n; i++)
        ans += dp[n][i];
    printf("%.10lf\n", ans);
}

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

int main(){
    string rev_s; cin >> rev_s;
    string s = rev_s;
    reverse(rev_s.begin(), rev_s.end());
    string key = "keyence";
    string rev_key = "ecneyek";
    int cnt=0, rev_cnt=0;
    int n = s.length();
  
    for(int i=0; i<n; i++){
        if(s[i] == key[cnt]){
            cnt++;
            if(cnt == 7){
                cout << "YES" << endl;
                return 0;
            }
        }else{
            break;
        }
    }
    for(int i=0; i<n; i++){
        if(rev_s[i] == rev_key[rev_cnt]){
            rev_cnt++;
            if(rev_cnt == 7){
                cout << "YES" << endl;
                return 0;
            }
        }else{
            break;
        }
    }
    if(cnt + rev_cnt >= 7){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 3628
<?php /*atcoder.php*/

$t = new temp();
$t->main();
unset($t);

class temp{
	private function lineIn(){
		return fgets(STDIN);
	}
	private function arrayIn(){
		return explode(" ", fgets(STDIN));
	}

	public function main(){
		$hinaMax = $this->lineIn();
		$hinaArare = $this->arrayIn();
		
		$type = "Three";

		foreach($hinaArare as $arare){
			if("Y" == $arare){
				$type = "Four";
				break;
			}
		}
		unset($arare);
		echo $type;	
	}
}
?>


Measured memory_bytes: 3828
#include <iostream>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        int ice[10];
        for (int i = 0; i < 10; i++) {
            ice[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            int p; cin >> p;
            ice[p]++;
        }
        for (int i = 0; i < 10; i++) {
            if (ice[i] == 0) {
                cout << '-'; 
            }
            for (int j = 0; j < ice[i]; j++) {
                cout << '*';
            }
            cout << endl;
        }
    }
    return 0;
}

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

int64_t N;
int64_t dfs(int64_t x, bool a, bool b, bool c){
  if(x>N){
    return 0;
  }
  int64_t k=0;
  if(a && b && c){
    k++;
  }
  k+=dfs(x*10+7, true, b, c);
  k+=dfs(x*10+5, a, true, c);
  k+=dfs(x*10+3, a, b, true);
  return k;
}
int main(){
  cin >> N;
  int64_t ans=dfs(0, false, false, false);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define  all(v)     (v).begin(),(v).end()
#define  rall(v)    (v).rbegin(),(v).rend()
#define  pb         push_back
#define  eb         emplace_back
#define  mp         make_pair
#define  ff         first
#define  ss         second
#define  pf         push_front
#define  bs         binary_search
#define  lb         lower_bound
#define  ub         upper_bound
#define  dec(x)   fixed<<setprecision(x)
#define  lcm(a,b)   (a*b/__gcd(a,b))
const ll inf=LLONG_MAX;
const ll mod=1e9+7;
const ld pi=acos(-1);
                    
void solution(){
   string s;
   cin>>s;
   ll ans=0;
   for(int i=0;i<s.size();i++){
       ans+=(s[i]-'0');
   }

   cout<<((ans%9==0)?"Yes":"No");
  
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    t=1;
   // cin>>t;
    while(t--){
        solution();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3684
$><<x=y=[0,2].zip(*P=$<.map{|l|l.split.map(&:to_i)<<l}).all?{|f,w,j|l=w,0
(1..P[0][2]).all?{|k|4.times{|i|P[~h=i/2][1][~k]==:UDLR[f+i&=1]&&l[h^=i]=4[g=i*2-l[h]]-g+-2[w+g]}
x,y=l
y<x}&&y<j&&j<=x}?:YES: :NO

Measured memory_bytes: 2628
#include <math.h>
#include <assert.h>

#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& v) {
    return is >> v.first >> v.second;
}

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (T& i: v) is >> i;
    return is;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
    return os << v.first << " " << v.second;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    int n = (int) v.size();
    for (int i = 0; i < n; ++i) os << v[i] << (i == n - 1 ? "" : " ");
    return os;
}

template <typename T>
void in(T& x) {
    std::cin >> x;
}

template <typename T1, typename... T2>
void in(T1 H, T2... T) {
    std::cin >> (H); in(T...);
}

template <typename T>
void out(const T H) {
    std::cout << (H);
}

template <typename T1, typename... T2>
void out(const T1 H, const T2... T) {
    std::cout << (H) << " "; out(T...);
}

template <typename T>
void eout(const char *s, const T H) {
    std::cerr << s << "=" << H << "\n";
}

template <typename T1, typename... T2>
void eout(const char *s, const T1 H, const T2... T) {
    while (*s != ',') std::cerr << *s++;
    std::cerr << "=" << H << " | "; eout(++s, T...);
}

#define nl                std::cout << "\n"
#define err(args...)      eout(#args, args)

#define rep(i, n)         for (int i =  0 ; i < (n); ++i)
#define per(i, n)         for (int i = (n) - 1; i > -1; --i)
#define repr(i, l, r)     for (int i = (l); i < (r); ++i)

#define sz(v)             ((int) v.size())
#define all(v)            (v).begin(), (v).end()
#define lla(v)            (v).rbegin(), (v).rend()

#define no                std::cout << "NO\n"
#define yes               std::cout << "YES\n"

const int INF           = 2147483647;
const long long int LNF = 9223372036854775807LL;

using ll  = long long int;
using vi  = std::vector<int>;
using vb  = std::vector<bool>;
using ii  = std::pair<int, int>;
using iii = std::pair< ii, int>;
using vii = std::vector<ii>;

const int N  = 505050;
const int MD = 1000*1000*1000 + 7;

int solve();
int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    //std::cout.tie(0);

    //int t; in(t); repr(tc, 1, t + 1)
    solve();

    return 0;
}

int solve() {
    int n; in(n);
    int q; in(q);
    vi adj[n];
    rep(i, n - 1) {
        int a; in(a); --a;
        int b; in(b); --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vi d(n, 0);
    rep(i, q) {
        int p; in(p);
        int x; in(x);
        d[p - 1] += x;
    }

    vi ans(n, 0);
    std::function<void(int, int, int)> dfs = [&](int u, int p, int a) {
        ans[u] += a;
        for (int v: adj[u]) if (v != p) {
            dfs(v, u, a + d[v]);
        }
    }; dfs(0, -1, d[0]);

    out(ans);

    return 0;
}


Measured memory_bytes: 31360
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

const int MOD = 1000000007;

template<class T>bool chmax(T &a, const T &b){
	if(a<b){
		a=b;
		return true;
	}
	return false;
}

template<class T>bool chmin(T &a, const T &b){
	if(a>b){
		a=b;
		return true;
	}
	return false;
}

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

void debug(VS &board){
	int h = board.size();
	rep(i,h){
		cout<<board.at(i)<<endl;
	}
	return;
}

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	int n;
	cin>>n;
	int ans = 0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(i%2 and a%2)
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main(){
  int N, K;
  int arr[1000] = {0};
  cin >> N >> K;
  for(int i=0; i<N; i++){
    cin >> arr[i];
  }
  int min;
  int min_j;
  for(int i=0; i<N-1; i++){
    min = arr[i];
    min_j = i;
    for(int j=i+1; j<N; j++){
      if(min > arr[j]){
        min = arr[j];
        min_j = j;
      }
    }
    if(min_j != i){
        int tmp = arr[i];
    	arr[i] = min;
    	arr[min_j] = tmp;
    }
  }
  
  int sum = 0;
  for(int i=0; i<K; i++){
    //cout << arr[i] << " ";
    sum += arr[i];
  }
  cout << sum << endl;
  
  
  
  return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
    using namespace std;
    #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define REP(i,x) for(int i=0;i<(int)(x);i++)
    #define REPS(i,x) for(int i=1;i<=(int)(x);i++)
    #define mp(a,b) make_pair(a, b)
    #define pb push_back
    #define eb emplace_back
    #define ll long long
    #define MAX 1000000007
    int main()
    { int t;
    cin>>t; int ar[t];
    ll s=0;
    for(int i=0;i<t;i++)
    {
        cin>>ar[i];
        s+=ar[i];
        s%=MAX;
    }ll a=0;
    for(int i=0;i<t-1;i++)
    {s=s-ar[i];
    if(s<0) s+=MAX;
        a+=(s)* ar[i];
        a%=MAX;
    }
    a%=MAX;
    cout<<a<<endl;
    }

Measured memory_bytes: 4408