akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>
#include<cmath>
#include <iomanip>
#include<stack>


#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)

#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e9

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef std::pair<ll, ll> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;

ll n;
vector< stack<P> > vs;
vector<ll> v;

void dfs(ll p, ll d)
{
    while(!vs[p].empty()){
        P top = vs[p].top();
        vs[p].pop();
        if(v[top.first] != 0) continue;
        else{
            v[top.first] = -1;
            if((top.second+d) % 2 == 0) v[top.first] = 1;
            dfs(top.first, d+top.second);
        }
    }
}


int main()
{
    cin >> n;
    vs.resize(n);
    v.resize(n);
    rep(i, n) v[i] = 0;

    rep(i, n-1){
        ll ut, vt, wt;
        P tmp1, tmp2;
        cin >> ut >> vt >> wt;
        ut--;
        vt--;
        tmp1.first = ut;
        tmp1.second = wt;
        tmp2.first = vt;
        tmp2.second = wt;
        vs[ut].push(tmp2);
        vs[vt].push(tmp1);
    }

    v[0] = 1;
    dfs(0, 0);
    rep(i, n){
        if(v[i] == 1) cout << 1 << endl;
        else cout << 0 << endl;
    }
}


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

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

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

    // start
    int x, y;
    cin >> x >> y;
    if (x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12)
        x = 1;
    else if (x == 4 || x == 6 || x == 9 || x == 11)
        x = 2;
    else
        x = 3;

    if (y == 1 || y == 3 || y == 5 || y == 7 || y == 8 || y == 10 || y == 12)
        y = 1;
    else if (y == 4 || y == 6 || y == 9 || y == 11)
        y = 2;
    else
        y = 3;

    if(x==y)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    // end

    return 0;
}


Measured memory_bytes: 384
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

fn main() {
    input! {
        n: u64
    }

    let mut ret = 0;
    for i in 1..10 {
        let c = i * 100 + i * 10 + i;
        if n <= c {
            ret = c;
            break;
        }
    }
    println!("{}", ret);
}

Measured memory_bytes: 4352
#include <iostream>
#include <bits/stdc++.h>
#define lc endl

using namespace std;

int main(){
    int N;
    cin >> N;
    int x;
    x = ((N + (1000-1)) / 1000) * 1000 - N;
    cout << x << lc;
    return 0;
}

Measured memory_bytes: 3544
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
int main()
{
    ll k;
    cin>>k;
    printf("50\n");
    if(k%50==0)
    {
        for(int i=0;i<49;i++)
            printf("%lld ",49+k/50);
        printf("%lld\n",49+k/50);
    }
    else
    {
        for(int i=0;i<k%50;i++)
        printf("%lld ",49+k/50+50-k%50+1);
        for(int i=k%50;i<50;i++)
        {
            if(i!=49)
                printf("%lld ",49+k/50-k%50);
            else
                printf("%lld\n",49+k/50-k%50);
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<tuple>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main() {
	string s;
	cin >> s;
	int ans = 0;
	rep(i, s.size()) {
		if (s[i] == '+') {
			ans++;
		}
		else {
			ans--;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<cmath>
#define LL long long
using namespace std;
inline void read(int &x){
	x=0;int f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();	}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=f;
}
int a,b;
int main()
{
	read(a),read(b);
	if(a<=b*2) cout<<0;
	else cout<<a-2*b;
}

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

using namespace std;

const double PI = 3.141592;
const int MAX_N = 1e5+5;
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;

const bool dbgEnabled = false;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef pair<string, ll> psi;
typedef pair<ll, string> pis;
typedef vector<pii> vpii;
typedef vector<psi> vpsi;
typedef vector<pis> vpis;
typedef vector<vi> vvi;

// Debug macros
#define dbg(x) do { \
	if (dbgEnabled) { cerr << #x << ": " << x << "\n"; } \
} while (0)

#define dbgv(x) do { \
	if (dbgEnabled) { cerr << #x << ": [ "; for (auto& _ : x) cerr << _ << " "; cerr << "]\n"; } \
} while (0)

#define dbgvv(x) do { \
	if (dbgEnabled) { cerr << #x << ":\n[\n"; for (auto& __ : x) dbgv(__); cerr << "]\n";} \
} while (0)

void solve() {
	ll n; cin >> n;
	vi a(n); for (auto &x : a) cin >> x;
	ll sum = 0;
	ll maxSoFar = a[0];
	for (auto &x : a) {
		if (x >= maxSoFar)
			maxSoFar = x;
		else {
			sum += maxSoFar - x;
		}
	}
	cout << sum << endl;
}

int main() {
	if (!dbgEnabled) {
		ios_base::sync_with_stdio(false);
		cin.tie(nullptr); cout.tie(nullptr);
	}
	
	ll t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}    
    return 0;
}



Measured memory_bytes: 4744
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            if a == b == c:
                S += a
            if a == b != c or a != b == c:
                S += 3*math.gcd(a,c)
            if a != b != c:
                S += 6*gcd(a, b, c)
print(S)

Measured memory_bytes: 9628
#include <bits/stdc++.h>
#define INF 1e9
#define MOD 1000000007
using namespace std;
using ll = long long;
using pii = pair<int, int>;

ll modpow(ll a, ll n, ll mod){
    ll res = 1;
    while( n > 0){
        if(n&1){
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main(void) {
    ll N;
    cin >> N;

    // ANS = ALL - ((Ai neq 0) + (Ai neq 9) - (Ai neq 0 & Aineq9))

    ll all = modpow(10, N, MOD);

    ll neq0 = modpow(9, N, MOD);
    ll neq09 = modpow(8, N, MOD);

    ll ans = all + MOD - (neq0 * 2 - neq09 + MOD) %MOD;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
def check(ary):
    for i in range(1, len(ary)):
        if ary[i] < ary[i - 1]:
            return False

    return True


def dfs(a, b, c, i):
    if len(b) + len(c) == 10:
        return check(b) and check(c)

    added_b = b[:]
    added_c = c[:]
    added_b.append(a[i])
    added_c.append(a[i])

    return dfs(a, added_b, c, i + 1) or dfs(a, b, added_c, i + 1)


def main():
    n = int(input())
    for i in range(n):
        datasets = [int(i) for i in input().split(' ')]
        result = dfs(datasets, [], [], 0)
        print('YES' if result else 'NO')


if __name__ == '__main__':
    main()



Measured memory_bytes: 5596
#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    int sum = 0;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        sum += a[i];
    }
    if (n - sum >= 0) {
        cout << n - sum << endl;
    }
    else {
        cout << -1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3612
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,K;
#define Maxn 200010
int p[Maxn];
int maxv[Maxn<<2],minv[Maxn<<2];
int sum[Maxn];
void Build_Tree(int k,int l,int r){
	if(l==r){
		maxv[k]=minv[k]=p[l];
		return;
	}
	int mid=(l+r)>>1;
	Build_Tree(k<<1,l,mid);
	Build_Tree(k<<1|1,mid+1,r);
	maxv[k]=max(maxv[k<<1],maxv[k<<1|1]);
	minv[k]=min(minv[k<<1],minv[k<<1|1]);
}
int qminv(int k,int l,int r,int L,int R){
	if(l==L&&r==R)return minv[k];
	int mid=(l+r)>>1;
	if(R<=mid)return qminv(k<<1,l,mid,L,R);
	else if(mid<L)return qminv(k<<1|1,mid+1,r,L,R);
	else return min(qminv(k<<1,l,mid,L,mid),qminv(k<<1|1,mid+1,r,mid+1,R)); 
}
int qmaxv(int k,int l,int r,int L,int R){
	if(l==L&&r==R)return maxv[k];
	int mid=(l+r)>>1;
	if(R<=mid)return qmaxv(k<<1,l,mid,L,R);
	else if(mid<L)return qmaxv(k<<1|1,mid+1,r,L,R);
	else return max(qmaxv(k<<1,l,mid,L,mid),qmaxv(k<<1|1,mid+1,r,mid+1,R));
}

struct Seg{
	int l,r;
}seg[Maxn],seq[Maxn];
int len1=0,len2=0;
bool flag=false;
inline bool Judge(int l,int r){return sum[r]-sum[l]==r-l;}

int main(){
	scanf("%d%d",&n,&K);
	for(register int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		sum[i]=sum[i-1];
		if(p[i]>p[i-1])sum[i]++;
	}
	Build_Tree(1,1,n);
	for(register int i=1;i<=n-K+1;++i)
	    if(Judge(i,i+K-1)){
			flag=true;
	    }else seq[++len1]=(Seg){i,i+K-1};
	for(register int i=1;i<=len1;++i){
		if(!len2)seg[++len2]=seq[i];
		else{
			while(len2){
				if(seg[len2].r<seq[i].l)break;
				int l1=seg[len2].l,r1=seg[len2].r,l2=seq[i].l,r2=seq[i].r;
				if(!Judge(l1,l2-1))break;
				if(!Judge(r1+1,r2))break;
				int num1=qminv(1,1,n,l2,r1);
				int num2=qmaxv(1,1,n,l2,r1);
				if(num1<p[l2-1])break;
				if(num2>p[r1+1])break;
				len2--;
			}
			seg[++len2]=seq[i];
		}
	}
	if(flag)printf("%d\n",len2+1);
	else printf("%d\n",len2);
	return 0;
}

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

#define ll long long
int main()
{
   int x,y;
   cin>>x>>y;
   if(y%2!=0){
     cout<<"No"<<endl;
     return 0;
   }
   int dorkar;
   if(y%4!=0){
        dorkar=(y/4)+1;

   }
   else{
      dorkar=y/4;
   }
   if(dorkar>x){
      cout<<"No"<<endl;
      return 0;
   }
   else{
     if((y/2)>=x) cout<<"Yes"<<endl;
     else cout<<"No"<<endl;
   }
    return 0;
}


Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long V = sc.nextLong();
		long B = sc.nextLong();
		long W = sc.nextLong();
		long T = sc.nextLong();
		long D = Math.abs(B - A);
		long VDiff = V - W;
		boolean f = true;
		if(VDiff <= 0){
			f = false;
		}else{
			if(VDiff * T >= D){
				f = true;
			}else{
				f = false;
			}
		}
		if(f){
			System.out.println("YES");
		}else{
			System.out.println("NO");			
		}
	}
}


Measured memory_bytes: 35816
N = int(input())
A = [int(i) for i in input().split()]
ans = 1
lim = 10 ** 18
if not (0 in A):
  for i in A:
    ans *= i
    if ans > lim:
      break
  if ans > lim:
    print(-1)
  else:
    print(ans)
else:
  print(0)

Measured memory_bytes: 21496
import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		scan.useDelimiter("\n");
		String str = "";
		String[] list;
		double[] math = new double[40];
		while(scan.hasNext()) {
			str = scan.nextLine();
			list = str.split(" ",0);
			int count = 0;
			for(String s : list) {
				if(s.equals("+")) {
					math[count-2] = math[count-2] + math[count-1];
					count--;
				}
				else if(s.equals("-")) {
					math[count-2] = math[count-2] - math[count-1];
					count--;
				}
				else if(s.equals("*")) {
					math[count-2] = math[count-2] * math[count-1];
					count--;
				}
				else if(s.equals("/")) {
					math[count-2] = math[count-2] / math[count-1];
					count--;
				}
				else {
					math[count] = Integer.parseInt(s);
					count++;
				}
				
			}
			System.out.println(math[0]);
		}

	}
}

Measured memory_bytes: 26212
function Main(input){
	var N = ~~input;
  var h = Math.floor(N / 7);
  for(var i = 0; i <= h; i++){
  	var a = N - i * 7;
    if(a % 4 == 0)return "Yes";
  }
  
  return "No";
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
14
`);

Measured memory_bytes: 7372
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    h,w = MII()
    d = [MII() for i in range(10)]
    wall = []
    for i in range(h):
        wall += MII()
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    ans = sum([d[w][1] for w in wall if w != -1])
    print(ans)

if __name__ == '__main__':
    main()

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

using namespace std;

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

const ll MAX = 1e18;

int main(){

  int N;
  cin >> N;

  vector<ll> A(N);

  rep(i,N){
    cin >> A.at(i);
  }

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

  __int128_t ans = 1;

  rep(i,N){
    ans *= A.at(i);
    if(ans > MAX){
      cout << -1 << endl;
      return 0;
    }
  }

  

  cout << (ll)ans << endl;

  return 0;
}

Measured memory_bytes: 3976
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pi;
const int MAXN=200005;
const int MOD=1000000007;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define fst first
#define snd second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())

int N,M;
vector<int>adj[MAXN];
bool vis[MAXN];
void dfs(int v){
	if(vis[v])return;
	vis[v]=true;
	for(auto i:adj[v]){
		dfs(i);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>N>>M;
	FOR(i,1,M){
		int a,b,c;cin>>a>>b>>c;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	int ans=0;
	FOR(i,1,N){
		if(!vis[i]){
			ans++;
			dfs(i);
		}
	}
	cout<<ans<<"\n";
}
/*
1 3
#.#


2 3
#.#
..#

3 3
##.
#.#
..#

3
2 5
6 1
3 7
Ans:6

4
3 7
2 9
8 16
10 8
Ans:9
*/


Measured memory_bytes: 11264
#!/usr/bin/env python3

n = int(input())
w = list(map(int, input().split()))

sum_w = sum(w)

ans = sum_w
value = 0

for i in range(0, n):
    value += w[i]
    ans_tmp = abs((sum_w-value)-value)
    ans = min(ans, ans_tmp)
print(ans)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include <string>
#include<cstdio>
#include<vector>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using namespace std;
typedef long long ll;
 
int main()
{
	string moji;
	int n; cin >> n;
	vector<int>a(10000);
	REP(i, 1000) { a[i] = 1; }
	REP(i, n) {
		char gomi;
		cin >> gomi; moji += gomi;
		if (gomi == '(') {
			a[i] = 1;
		}
		else {
			a[i] = 0;
		}
	}
	int sii = moji.size();
	while (1) {
		int c = 0;
		REP(i, n - 1) {
 
			if (a[i] == 1 && a[i + 1] == 0) {
				a.erase(a.begin() + i, a.begin() + i + 2);
				sii -= 2;
				c++;
			}
		}
		if (c == 0) {
			REP(i, sii) {
				int aa = a[i];
				if (aa) {
					moji = moji + ')';
				}
				else {
					moji = '(' + moji;
				}
			}
			break;
		}
	}
	cout << moji << endl;
	return 0;
}
 

Measured memory_bytes: 256
def f(t,_t):
    h,m=[int(_t[i:i+2])-int(t[i:i+2])for i in[0,3]]
    return 60*h+m
n,t=map(int,input().split())
prv=input().split()
a=[]
for _ in [0]*(n-1):
    now=input().split()
    d=f(prv[2],now[0])
    if d>=t:
        a.append(now[1]+' '+str(d))
    prv=now
print(len(a))
for x in a:print(x)

Measured memory_bytes: 7672
import itertools

s = int(input())
L = list(map(int,input().split()))

L = sorted(L,reverse=True)

M = list(itertools.combinations(L, 3))
#print(M)
#M = list(set(M))
#print(M)

c = 0
for i,j,k in M:
    #print(i,j,k)
    
    if i!=j and j !=k and i < j+k:
        #print(i,j,k)
        c += 1
        
print(c)

Measured memory_bytes: 20624
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx


using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define iinf (3000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
int main(){
	std::ios::sync_with_stdio(false);
	string s,ans1,ans="zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz",t;
	cin>>s>>t;
	int i,j;
	rep(i,s.length()){
		ans1.clear();
		rep(j,t.length()){
			if(j+i>=s.length())
				break;
			if(s[j+i]=='?'||s[j+i]==t[j])
				continue;
			else
				break;
		}
		if(j==t.length()){
			//cout<<i<<endl;
			rep(j,i){
				if(s[j]=='?'){
					ans1+='a';
				}
				else
					ans1+=s[j];
			}
			f(j,i,i+t.length()){
				ans1+=t[j-i];
			}
			f(j,i+t.length(),s.length()){
				if(s[j]=='?'){
					ans1+='a';
				}
				else
					ans1+=s[j];
			}
			//cout<<ans<<" "<<ans1<<endl;
			ans=min(ans,ans1);
		}
	}
	if(ans!="zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz")
	cout<<ans<<endl;
else cout<<"UNRESTORABLE"<<endl;
} 


Measured memory_bytes: 256
import math
s,l,h,m=map(int,input().split())
#JIKOKU
t=60*h+m
#TANSHIN KAKUDO
sd=(0.5*t)%360
ld=(6*t)%360
x=abs(sd-ld)

if x==180:
    print(s+l)
    exit()
elif x==0:
    print(abs(l-s))
    exit()
else:
    x=min(x,360-x)

radx=math.radians(x)
cosx=math.cos(radx)

print((s**2+l**2-2*l*s*cosx)**0.5)



Measured memory_bytes: 9580
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

int main(){
	string s;
	cin >> s;
	for (int i = 0; i < s.length()-1; i++){
		if (s[i] == s[i+1]){
			cout << "Bad" << endl;
			return 0;
		}
	}
	cout << "Good" << endl;
	return 0;
}



Measured memory_bytes: 256
N = gets.to_i

restaurant = []

N.times do |n|
  restaurant << gets.split
  restaurant[n][1] = restaurant[n][1].to_i
  restaurant[n] << n+1
end

restaurant.sort_by { | r |
  [r[0], -r[1]] 
}.each { | r | puts r[2] }


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int const M=2e5+10,mod=1e9+7,inf=1e9+10;
vector<int>adj[M];
int a[M];
int mo[M],mo2[M],cnt=0;
void dfs(int v)
{
	mo[v]=cnt;
	mo2[a[v]]=cnt;
	for(int i=0;i<adj[v].size();i++)
	{
		int u=adj[v][i];
		if(!mo[u])dfs(u);
	}
}
main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!mo[i])++cnt,dfs(i);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(mo[i]==mo2[i])ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 13952
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

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

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    vector<ll> a(n),b(n);
    rep(i,n)cin >> a[i] >> b[i];
    sort(ALL(a));
    sort(ALL(b));
    if(n%2==0){
        ll mi = a[n/2 - 1] + a[n/2];
        ll mx = b[n/2 - 1] + b[n/2];
        cout << mx - mi + 1 << endl;
    }else{
        ll mi = a[n/2], ma = b[n/2];
        cout << ma - mi + 1 << endl;
    }
}

Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
 
int h, w;
vector<string> v;
int dir[4][2] = { { 0,-1 },{ -1,0 },{ 1,0 },{ 0,1 } };
struct node
{
	int x, y;
	int step;
	node(int _x, int _y ):x(_x),y(_y), step(0){}
	node():x(0),y(0),step(0){}
};
bool check(node n)
{
	return n.x >= 0 && n.x < h&&n.y >= 0 && n.y < w&&v[n.x][n.y]!='#';
}
int bfs(node no)
{
	queue<node> q;
	node  t, n;
	v[no.x][no.y] = '#';
	q.push(no);
	while(!q.empty())
	{
		t = q.front();
		q.pop();
		if (t.x == h-1 && t.y == w-1)
			return t.step;
		for(int k=0;k<4;k++)
		{
			n = t;
			n.x += dir[k][0], n.y += dir[k][1];
			if (check(n))
			{
				v[n.x][n.y] = '#';
				n.step++;
				q.push(n);
			}
		}
	}
	return -1;
 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> h >> w;
	v.clear();
	v.resize(h);
 
	for (int i = 0; i < h; i++)
		cin >> v[i];
 
	int count = 0;
	for (auto i : v)
		for (auto j : i)
			if (j == '#')
				count++;
	int res=bfs(node(0,0));
	cout << (res!=-1 ? h * w - count -res-1 : -1) << endl;
	return 0;
}

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

#define ff first
#define ss second
#define ll long long
#define pq priority_queue
#define mii map<int,int>

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef set<int> si;
typedef vector<vi> vii;
typedef vector<ii> vpi;
typedef vector<ll> vll;
int oo = (1e9) + 7;

int h, w;
char mat[1005][1005];
int tb[1005][1005];

int dp(int i, int j) {
    if(i == h-1 and j == w-1) return 1;
    if(i > h-1 or j > w-1) return 0;
    if(tb[i][j] != -1) return tb[i][j];

    int ans = 0;
    if(mat[i+1][j] != '#') ans = ans%oo + dp(i+1, j)%oo;
    if(mat[i][j+1] != '#') ans = ans%oo + dp(i, j+1)%oo;

    tb[i][j] = ans % oo;
    return ans % oo;
}

int main() {
    cin >> h >> w;

    
    for(int i = 0; i < h; i++)
    {
        scanf(" %s", mat[i]);
    }
    memset(tb, -1, sizeof tb);
    int ans = dp(0, 0);
    printf("%d\n", dp(0, 0));


    return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template<typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template<typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template<typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template<typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template<typename T> inline T power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  pqdesc<int> q;
  int N; cin >> N;
  vi32 cnt(100001);
  rep(i, N) {
    int a; cin >> a;
    cnt[a]++;
  }
  rep(i, 100001) if (cnt[i] > 0) q.push(cnt[i]);
  while (q.top() > 1) {
    auto c = q.top(); q.pop();
    if (c >= 3) {
      q.push(c - 2);
    } else if (c == 2) {
      auto c2 = q.top(); q.pop();
      if (c2 == 2) {
        q.push(1), q.push(1);
      } else {
        q.push(1);
      }
    }
  }
  cout << q.size() << '\n';
}


Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////

int main(){
    ll n;cin>>n;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll h=a[0]-1;
    bool f=true;
    rep(i,1,n-1){
        if(h>a[i])f=false;
        else if(h<a[i])h=a[i]-1;
    }
    if(f)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

















Measured memory_bytes: 1024
#include<cstdio>
#include<set>
long long m[100001],lsum[100001],rsum[100001]; 
int main(){
    int n;
    scanf("%d",&n);
    long long tmp;
    std::multiset<long long> l;
    std::multiset<long long,std::greater<long long>> r;
    lsum[0]=0;
    for(int i=0;i<n;i++){
        scanf("%lld",&tmp);
        l.insert(tmp);
        lsum[0]+=tmp;
    }
    for(int i=0;i<n;i++)scanf("%lld",&m[i]);
    rsum[n]=0;
    for(int i=0;i<n;i++){
        scanf("%lld",&tmp);
        r.insert(tmp);
        rsum[n]+=tmp;
    }
    for(int i=0;i<n;i++){
        tmp=*(l.begin());
        if(tmp<m[i]){
            l.erase(l.equal_range(tmp).first);
            l.insert(m[i]);
            lsum[i+1]=lsum[i]+m[i]-tmp;
        }else{
            lsum[i+1]=lsum[i];
        }
    }
    for(int i=n;i>0;i--){
        tmp=*(r.begin());
        if(tmp>m[i-1]){
            r.erase(r.equal_range(tmp).first);
            r.insert(m[i-1]);
            rsum[i-1]=rsum[i]+m[i-1]-tmp;
        }else{
            rsum[i-1]=rsum[i];
        }
    }
    long long ans=lsum[0]-rsum[0];
    for(int i=1;i<=n;i++){
        ans=std::max(ans,lsum[i]-rsum[i]);
    }
    printf("%lld",ans);
    return 0;
}

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

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

using ll = long long;
using P = pair<ll,ll>;
using grid = vector<vector<int>>;

const int dx[2] = {1, 0};
const int dy[2] = {0, 1};
const int INF = 1<<30;
const ll mod = 998244353LL;

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

int main() {
    ll M,K;
    cin>>M>>K;
    if((1LL<<M)<=K)cout<<-1<<endl;
    else if(M==0){
        if(K==0) cout<<0<<" "<<0<<endl;
        else cout<<-1<<endl;
    }
    else if(M==1) {
        if(K==0) cout<<0<<" "<<0<<" "<<1<<" "<<1<<endl;
        else cout<<-1<<endl;
    }
    else {
        vector<ll> ans(1LL<<(M+1),0);
        ans[0] = K;
        ll N = (1LL<<(M+1));
        for(ll i = 1; i<=(1LL<<(M))-1; i++){
            if(i<=K) ans[i] = ans[N-i] = i-1;
            else ans[i] = ans[N-i] = i;
        }
        ans[(1LL<<M)]=K;
        for(auto x:ans) cout<<x<<" ";
        cout<<endl;
    }
}

Measured memory_bytes: 5288
#include <iostream>
#include <string>
#include<iomanip>
#include <algorithm>
#include <map>
#include <vector>
#include<queue>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include <map>
#include<string.h>
#include<sstream>
#include<stack>
#include<unordered_map>
#include <iostream>
#include <stdio.h>
#include <ctype.h>
#include <cstdio>
#include <cstdlib>
#define ll long long
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define arr2dof vector  vector<vector<int>>dp(N,vector<int>(2, inf));
using namespace std;
const int N = 2e5 + 5, inf = 1e9+7 ;
const double ep = 0.0000000001;
const double pi = 3.14159265359;
const long long inff= 1e18;
vector < vector<int>>graph;
int n, m,a,b;
int dp[100005];
bool visited[100005];
void dfs(int node) {
	visited[node] = true;
	for (int child : graph[node]) {
		if (!visited[child]) 
		dfs(child);
		
		
			dp[node] = max(dp[node], 1 + dp[child]);
		
	}
}


int main()
{
	
	cin >> n>>m;
	graph.resize(max(n,m) + 5);
	
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		graph[a].push_back(b);
	
	}
	for (int i = 1; i <= n; ++i) {
		if (!visited[i])
			dfs(i);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 8192
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const ll INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

class data{
	public:
		int r;
		int t;
		int a;
		int w;
		data(int r, int t, int a, int w):r(r), t(t), a(a), w(w){}
		data(){}
};

bool compare(const data &a, const data &b){
	return a.r+a.t > b.r+b.t || (a.r+a.t==b.r+b.t&&a.t>b.t);
}

int n;
vector<data> line;

vector<vector<vector<int>>> dp(2000, vector<vector<int>>(2000, vector<int>(2, -1)));

int func(int place, int time, int used){
	if(place==n){
		return 0;
	}
	if(time==0)return 0;
	if(dp[place][time][used]>=0)return dp[place][time][used];
	int res = 0;
	if(time>=line[place].r){
		if(used){
			res = max(res, func(place, time - line[place].r, 1) + line[place].w);

		}else{
			res = max(res, func(place, min(line[place].t-1, time - line[place].r), 1) + line[place].a);
		}
	}
	res = max(res, func(place+1, time, 0));
	res = max(res, func(place, time-1, used));
	return dp[place][time][used] = res;
}

int main(){
	cin >> n;
	rep(i, n){
		int r, t, a, w;
		cin >> r >> a >> w >> t;
		line.emplace_back(r, t, a, w);
	}
	
	sort(all(line), compare);
	
	int ans = 0;

	rep(i, n){
		ans = max(ans, func(i, line[i].t-1, 1) + line[i].a);
	}

	cout << ans << endl;




	return 0;
}



Measured memory_bytes: 222012
import java.util.*;

class Main{
    static Scanner sc = new Scanner(System.in);
    public static void main(String args[]){
        int A=sc.nextInt(),B=sc.nextInt(),res=0,r=1;
        while(r<B){
            res++;
            r+=A-1;
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 35632
R = lambda type_ = "int": list(map(eval(type_), input().split(' ')))

N, Y = R()
Y //= 1000

a, b, c = -1, -1, -1
for i in range(N + 1):
    for j in range(N - i + 1):
        if Y - i * 10 - j * 5 == N - i - j:
            a = i
            b = j
            break

if a != -1:
    c = N - a - b
print('{} {} {}'.format(a, b, c))



Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <set>
using namespace std;
#define mod (long)(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<long> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } long C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int main(){
    int N;
    cin >> N;
    pair<long, long> dish[N];
    for(int i = 0; i < N; i++){
        long A, B;
        cin >> A >> B;
        dish[i].first = A + B;
        dish[i].second = A;
    }
    sort(dish, dish + N, greater<>());
    long ans = 0;
    for(int i = 0; i < N; i++){
        if(i % 2){
            ans -= dish[i].first - dish[i].second;
        }else{
            ans += dish[i].second;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define LOOP(val, times)   for(val = 0; val < (times); val++)
int main(){
  long long n;
  cin>>n;
  double h=sqrt(n)+0.5;
  long long hh=(long long)h;
  long long dd=hh;
  long long ff=1;

  for(long long i=hh;i>0;i--){
  
    if(n%i==0){
      dd=i;
      ff=n/i;
      break;
    }
  }
  cout<<dd+ff-2<<endl;
}

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

long long a[505];
// imos
long long b[505];
// dp[i][j] := iまでをj区間にした時の最大値
double dp[505][505];

double rec(int n, int m){
	if (dp[n][m] != 0) return dp[n][m];
	double res = 0;
	if (m == 1) return dp[n][m] = b[n]/(double)n;
	for (int i = n-1; i > 0; i--){
		double tmp = rec(i, m-1) + (b[n] - b[i])/(double)(n-i);
		res = max(res, tmp);
	}
	res = max(res, b[n]/(double)n);
	return dp[n][m] = res;
}

int main() {
	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	for (int i = 2; i <= N; i++){
		b[i] += b[i-1];
	}
	printf("%f\n", rec(N, M));
	
	return 0;
}


Measured memory_bytes: 5248
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = input_int()
    p = input_to_int_tuple()

    cnt = 0
    pre_min = 10 ** 6
    for i in range(n):

        if i == 0 or p[i] <= pre_min:
            cnt += 1

        pre_min = min(pre_min, p[i])

        # temp = True
        # for j in range(i):
        #     if p[i] > p[j]:
        #         temp = False
        #         break
        # if temp:
        #     cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 24872
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

int digit(int64 n){
  int res=0;
  while(n>0){
    res++;
    n/=10;
  }
  return res;
}

void run(void){
  int64 n;
  scanf("%lld",&n);
  int min=digit(n);
  int i;
  for(i=1;(int64)i*i<=n;i++){
    if(n%i!=0) continue;
    int64 a=i;
    int64 b=n/i;
    min=MIN(min,MAX(digit(a),digit(b)));
  }
  printf("%d\n",min);
}

int main(void){
  run();
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int N=1010;
int d[N][N],chk[N][N],qs,qe;
pii q[N*N];
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)d[i][j]=2012345678;
	for(int i=0;i<n;i++){
		static char buf[N];scanf("%s",buf);
		for(int j=0;j<m;j++)if(buf[j]=='#'){
			d[i][j]=0;
			q[qe++]={i,j};
			chk[i][j]=1;
		}
	}
	while(qs<qe){
		auto p=q[qs++];int i,j;tie(i,j)=p;
		if(i&&!chk[i-1][j]){
			d[i-1][j]=d[i][j]+1;
			q[qe++]={i-1,j};
			chk[i-1][j]=1;
		}
		if(j&&!chk[i][j-1]){
			d[i][j-1]=d[i][j]+1;
			q[qe++]={i,j-1};
			chk[i][j-1]=1;
		}
		if(i<n-1&&!chk[i+1][j]){
			d[i+1][j]=d[i][j]+1;
			q[qe++]={i+1,j};
			chk[i+1][j]=1;
		}
		if(j<m-1&&!chk[i][j+1]){
			d[i][j+1]=d[i][j]+1;
			q[qe++]={i,j+1};
			chk[i][j+1]=1;
		}
	}
	int M=0;
	for(int i=0;i<n;i++)M=max(M,*max_element(d[i],d[i]+m));
	printf("%d\n",M);
}

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

int main()
{
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  while(true)
  {
    C -= B;
    if(C <= 0)
    {
      cout << "Yes" << endl;
      break;
    }
    A -= D;
    if(A <= 0)
    {
      cout << "No" << endl;
      break;
    }
  }
}

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

using namespace std;

int main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K, d, A;
  cin >> N >> K;
  bool find[N + 1] = {false};
  for (int i = 0; i < K; i++){
    cin >> d;
    for (int j = 0; j < d; j++){
      cin >> A;
      if (!find[A]){
	N--;
	find[A] = true;
      }
    }
  }
  cout << N << '\n';
  return 0;
}



Measured memory_bytes: 3628
from collections import defaultdict

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = defaultdict(int)
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

A, B, C = map(int, input().split())
if A == B and B == C:
    if A % 2 == 1:
        print(0)
    else:
        print(-1)
else:
    fac_2_A = prime_factorization(A)[2]
    fac_2_B = prime_factorization(B)[2]
    fac_2_C = prime_factorization(C)[2]
    ans = min(fac_2_A, fac_2_B, fac_2_C)
    if fac_2_A == fac_2_B and fac_2_B == fac_2_C:
        ans += 1
    print(ans)

Measured memory_bytes: 3316
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[]$) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] b = new int[n][n];
        int[] wait = new int[n + 1];
        wait[n] = n;
        Deque<Integer>[] deque = new Deque[n];
        for (int i = 0; i < n; i++) {
            deque[i] = new ArrayDeque<>();
            wait[i] = scanner.nextInt() - 1;
            for (int j = 2; j < n; j++) {
                deque[i].add(scanner.nextInt() - 1);
            }
        }
        int[] lastMatch = new int[n];
        int rem = n;
        while (rem > 0) {
            boolean updated = false;
            for (int i = 0; i < n; i++) {
                if (wait[wait[i]] == i) {
                    lastMatch[wait[i]] = lastMatch[i] = Math.max(lastMatch[wait[i]], lastMatch[i]) + 1;
                    updated = true;
                    if (!deque[wait[i]].isEmpty()) {
                        wait[wait[i]] = deque[wait[i]].poll();
                    } else {
                        wait[wait[i]] = n;
                        rem--;
                    }
                    if (!deque[i].isEmpty()) {
                        wait[i] = n;
                        wait[i] = deque[i].poll();
                    } else {
                        rem--;
                    }
                }
            }
            if (!updated) {
                System.out.println(-1);
                return;
            }
        }
        Arrays.stream(lastMatch).max().ifPresent(System.out::println);
    }
    
}


Measured memory_bytes: 273428
conv = lambda t: (t // 100)*60 + (t % 100)
while 1:
    N, P, Q = map(int, input().split())
    if N == P == Q == 0:
        break
    P = conv(P); Q = conv(Q)
    CM = [0]*(Q-P+1)
    for i in range(N):
        k = int(input())
        *T, = map(int, input().split())
        for s, t in zip(T[::2], T[1::2]):
            s = conv(s); t = conv(t)
            CM[s-P] += 1
            CM[t-P] -= 1
    cnt = ans = 0
    for i in range(Q-P):
        CM[i+1] += CM[i]
        if CM[i] < N:
            cnt += 1
        else:
            cnt = 0
        ans = max(ans, cnt)
    print(ans)



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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (max(a, c) - min(a, c) <= d) {
    cout << "Yes" << endl;
  }
  else if (max(a, b) - min(a, b) <= d && max(b, c) - min(b, c) <= d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define mk make_pair
const int N=200010;
int n, m;
vector<pair<int, pair<int, int>> > v[N], v1[N];
int main(){
	int t;
	cin>>t;
	while(t--){
		scanf("%d",&n);
		int k, l, r;
		ll ans=0;
		for(int i=0; i<=n+1; ++i){
			v[i].clear();
			v1[i].clear();
		}
		multiset<pair<int, pair<int, int>>>s;
		for(int i=0; i<n; ++i){
			scanf("%d%d%d",&k,&l,&r);
			if(r>=l){
				v1[k+1].push_back(mk(-(r-l), mk(-r, -l)));
			}
			else{
				v[k].push_back(mk(-(l-r), mk(-l, -r)));
			}
		}
		for(int i=n; i>=1; --i){
			for(auto it:v[i])s.insert(it);
				if(s.size()>0){
					ans-=s.begin()->second.first;
					s.erase(s.begin());
				}
		}
		while(s.size()>0){
				ans-=s.begin()->second.second;
				s.erase(s.begin());
		}
		for(int i=1; i<=n; ++i){
			for(auto it:v1[i])s.insert(it);
				if(s.size()>0){
					ans-=s.begin()->second.first;
					s.erase(s.begin());
				}
		}
		while(s.size()>0){
				ans-=s.begin()->second.second;
				s.erase(s.begin());
		}
		for(auto it:v1[n+1])ans-=it.second.second;
		for(auto it:v[0])ans-=it.second.second;
		printf("%lld\n",ans);
	}
}

Measured memory_bytes: 18816
from collections import Counter

def is_strait(_cnt):
    f = 0
    for i in range(14):
        if _cnt[(i % 13) + 1] == 1:
            f += 1
            if f == 5:
                return True
        else:
            f = 0
    return False

try:
    while 1:
        cnt = Counter(map(int,input().split(',')))
        mc = cnt.most_common(2)
        if mc[0][1] == 4:
            print('four card')
        elif mc[0][1] == 3 and mc[1][1] == 2:
            print('full house')
        elif mc[0][1] == 3:
            print('three card')
        elif mc[0][1] == mc[1][1] == 2:
            print('two pair')
        elif mc[0][1] == 2:
            print('one pair')
        elif is_strait(cnt):
            print('straight')
        else:
            print('null')
except:
    pass

Measured memory_bytes: 8008