akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int c[]={0,2,5,5,4,5,6,3,7,6};
string stmax(string a, string b)
{
  if(a.size() > b.size())
  {
    return a;
  }
  else if(a.size() < b.size())
  {
      return b;
  }
  else{
  	if(a>=b)return a;
    else return b;
  }
}
    
int main(){
  int n,m;
  cin>>n>>m;
  int a[m];
  for(int i=0; i<m; i++){
    cin>>a[i];
  }
  vector<string>dp(10101,"");
  for(int i=0; i<=n; i++){
    for(int j=0; j<m; j++){
      if(i==0||dp[i]!=""){			//
        dp[i+c[a[j]]]=stmax(dp[i]+to_string(a[j]),dp[i+c[a[j]]]);
      }
    }
  }
  cout<<dp[n]<<endl;
}
    
  
   


Measured memory_bytes: 33024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto&& V : v)
#define all(x) (x).begin(), (x).end()
using lint = long long;
const int INF = 1 << 29;
const double EPS = 1e-9;
using namespace std;

int main(void) {
  int n, k;
  cin >> n >> k;
  vector<double> ans(n + 1);
  vector<int> times_memo;
  times_memo.push_back(1);
  for (int i = 1;; ++i) {
    int value = times_memo.back() * 2;
    times_memo.push_back(value);
    if (value >= k) break;
  }
  map<int, int> times;
  rep1(i, n) {
    int ntimes = distance(times_memo.begin(), lower_bound(all(times_memo), (k + i - 1) / i));
    ++times[ntimes];
  }
  double sum = 0;
  allrep(m, times) {
    sum += pow(0.5, m.first) * m.second;
  }
  sum /= n;
  cout << fixed << setprecision(15) << sum << endl;
  return 0;
}

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int res[1000001];

int calc(int A){
    string strA = to_string(A);
    if(strA.length() == 1) return A;
    int ret = 0;
    for(int i = 1; i < strA.length(); i++){
        string S = strA.substr(0, i);
        string T = strA.substr(i);
        ret = max(ret, stoi(S, nullptr, 10) * stoi(T, nullptr, 10));
    }
    return ret;
}

int calc2(int A){
    if(A <= 9) return A;
    int ret = 0;
    int md = 10;
    while(md <= A){
        int a = A % md;
        int b = A / md;
        ret = max(ret, a*b);
        md *= 10;
    }
    return ret;
}

int solve(int A){
    int temp = calc2(A);
    if(res[temp] != -1) return res[A] = res[temp] + 1;

    if(A == temp) return res[A] = 0;
    else return res[A] = solve(temp) + 1;
}

int main(void){
    rep(i, 1000001) res[i] = -1;
    
    for(int i = 0; i <= 1000000; i++){
        //if(i % 10000 == 0) cout << i << endl;
        if(res[i] == -1) solve(i);
    }
    vector<int> ans;
    int Q;cin >> Q;
    rep(i, Q){
        int a; cin >> a;
        ans.push_back(res[a]);
    }
    rep(i, ans.size()) cout << ans[i] << endl;
    
    return 0;
}


Measured memory_bytes: 7076
#pragma GCC optimize("Ofast")

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> X(N), Y(N), P(N);
  for(int i = 0; i < N; ++i){
    cin >> X[i] >> Y[i] >> P[i];
  }
  const int INF = 1e9+1;
  int t = (1<<N)-1;
  vector<long long> ans(N+1,1e18);

  vector<vector<long long>> DX(1<<N,vector<long long>(N,INF)), DY = DX;
  for(int i = 0; i < (1<<N); ++i){
    vector<long long> XX = {-INF,0,INF};
    for(int l = 0; l < N; ++l){
      if(i>>l&1){
        XX.emplace_back(X[l]);
      }
    }
    sort(XX.begin(), XX.end());
    for(int l = 0; l < N; ++l){
      auto xlb = lower_bound(XX.begin(), XX.end(), X[l]);
      long long dx = (*xlb)-X[l];
      dx = min(dx,X[l]-(*prev(xlb)));
      DX[i][l] = dx;
    }
    
    vector<long long> YY = {-INF,0,INF};
    for(int l = 0; l < N; ++l){
      if(i>>l&1){
        YY.emplace_back(Y[l]);
      }
    }
    sort(YY.begin(), YY.end());
    long long s = 0;
    for(int l = 0; l < N; ++l){
      auto ylb = lower_bound(YY.begin(), YY.end(), Y[l]);
      long long dy = (*ylb)-Y[l];
      dy = min(dy,Y[l]-(*prev(ylb)));
      DY[i][l] = dy;
    }
  }
  
  for(int i = 0; i < (1<<N); ++i){
    int u = t^i;
    for(int k = u; ; k = (k-1)&u){

      int p = __builtin_popcount(i|k);
      long long s = 0;
      for(int l = 0; l < N; ++l){
        s += min(DX[i][l],DY[k][l])*P[l];
        if(s >= ans[p]) break;
      }
      ans[p] = min(ans[p],s);
      if(!k) break;
    }
  }
  for(auto e : ans)
    cout << e << "\n";
}


Measured memory_bytes: 13000
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>
    
using namespace std;

typedef long long ll;


int main() {
    int n;
    ll a[100010], b[100010],d[100010];
    ll s = 0;
    vector<int> k;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        d[i] = b[i] - a[i];
        s += d[i];
    }
    
    if (s > 0) {
        cout << -1 << endl;
        return 0;
    }
    int l = 0;
    sort(d,d+n,greater<int>());
    int m = 0;
    if (d[0] <= 0) {
        cout << 0 << endl;
        return 0;
    }
    while (d[m] > 0) {
        if (d[m] < -d[n-1-l]) {
            d[n-1-l] += d[m];
            m++;
            
        } else {
            d[m] += d[n-1-l];
            l++;
        }
    }
    
    cout << m + l + 1 << endl;
}

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

vector<ll>res;

void prime_factor(ll n){
    for(int i=2; i*i<=n; i++){
		ll tmp=0;
        while(n%i==0){
			tmp++;
            n/=i;
        }
		if(tmp!=0) res.push_back(tmp);
    }
    if(n!=1) res.push_back(1);
    return;
}

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

ll combination(ll n,ll m,ll mod){
	ll nume=1; //分子
	for(int i=0;i<m;i++){
		nume=nume*(n-i)%mod;
	}
	ll deno=1; //分母
	for(int i=1;i<=m;i++){
		deno=deno*i%mod;
	}
	ll res=nume*pow(deno,mod-2,mod);
	res%=mod;
	return res;
}

int main(){
	ll n,m,ans=1,mod=1000000007;
	cin>>n>>m;
	prime_factor(m);
	for(ll i=0;i<res.size();i++){
		ans*=combination(res[i]+n-1,res[i],mod);
		ans%=mod;
	}
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<int> a;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    reverse(a.begin(),a.end());
    vector<int> ans(n);
    int tmp=0;
    for(int i=0; i<n; i++){
        if(i%2==0){
            ans[tmp] = a[i];
        }else{
            ans[n-tmp-1] = a[i];
            tmp++;
        }
    }
    rep(i,n) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const int mod=(int)1e9+7;
vector<int>v[200001];
bool visit[200001];
int ctr=0,f=0,n,mi=1e9,flag=0,d[200001];
queue<int>q;
void bfs(int x)
{
        d[x]=0;
        q.push(x);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int y=0;y<v[u].size();y++)
            {
                if(d[v[u][y]]==-1)
                {
                    d[v[u][y]]=d[u]+1;
                    q.push(v[u][y]);
                }
            }
        }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    memset(visit,0,sizeof(visit));
    memset(d,-1,sizeof(d));
    int m;
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(1);
    if(d[n]==-1) cout<<"IMPOSSIBLE";
    else{
        if(d[n]!=2) cout<<"IMPOSSIBLE";
        else cout<<"POSSIBLE";
    }
	return 0;
}


Measured memory_bytes: 13424
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef set <int> si;
typedef set <int> :: iterator sitr;
typedef set <ll> :: iterator sltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef mset <int> :: iterator msitr;
typedef mset <ll> :: iterator msltr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newline '\n'
char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
void IO(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
// end of Template
int n,i;
int main(){
    // IO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>i;
    cout<<n-i+1<<newline;
}


Measured memory_bytes: 256
A, B, C, X, Y = map(int, input().split())

pizza = {X : A, Y : B}
ans = 0

for i in range(max(X, Y)):
    if i <= min(X, Y) - 1:
        ans += min(A + B, 2 * C)
    else:
        ans += min(pizza[max(X, Y)], 2 * C)

print(ans)

Measured memory_bytes: 39152
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// ここまで

#[derive(Eq, PartialEq)]
struct State {
    v: usize,
    d: u64,
}

use std::cmp::Ordering;
impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        other.d.cmp(&self.d)
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

fn dijkstra(src: usize, g: &Vec<Vec<(usize, u32)>>) -> Vec<u64> {
    let inf: u64 = 10000000000000000;
    let mut dp = vec![inf; g.len()];
    dp[src] = 0;
    let mut h = std::collections::BinaryHeap::new();
    h.push((src, 0));
    while let Some((v, d)) = h.pop() {
        if d > dp[v] {
            continue;
        }
        for &(u, t) in &g[v] {
            let c = d + t as u64;
            if c < dp[u] {
                dp[u] = c;
                h.push((u, c));
            }
        }
    }
    dp
}

use std::io::BufWriter;
use std::io::Write;

fn run() {
    input! {
        n: usize,
        m: usize,
        s: usize1,
        t: usize1,
        e: [(usize1, usize1, u32, u32); m],
    }
    let mut g = vec![vec![]; n];
    let mut h = vec![vec![]; n];
    for (u, v, a, b) in e {
        g[u].push((v, a));
        g[v].push((u, a));
        h[u].push((v, b));
        h[v].push((u, b));
    }
    let x = dijkstra(s, &g);
    let y = dijkstra(t, &h);
    let mut prev = 0;
    let mut ans = vec![0; n];
    for ((x, y), dp) in x.iter().zip(y.iter()).zip(ans.iter_mut()).rev() {
        let z = 1000000000000000 - (*x + *y);
        prev = std::cmp::max(prev, z);
        *dp = prev;
    }
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    for ans in ans {
        writeln!(out, "{}", ans).unwrap();
    }
}

fn main() {
    run();
}


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

int main(){
	int n,k,num;
	cin >> n >> k;
	num = 1;
	for(int i=1; i<=n; i++){
		if(2*num < num+k) num = 2*num;
		else num = num + k;
	}
	cout << num <<endl;
	return 0;
}


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

int main(){
  int n,d,ans;
  cin >> n;
  cin >> d >> ans;
  for(int i=0; i<n; i++){
    int count;
    int a;
    cin >> a;
    for(int j=0;(a*j+1)<=d;j++){
      count = j+1;
    }
    ans += count;
  }
  cout << ans << endl;
}
      
      
  

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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)
#define rep1(i,n) rep(i,1,n+1)
#define repR(i,s,n) for(ll i = (n-1); i >= (s); i--)
#define repR0(i,n) repR(i,0,n)
#define repR1(i,n) repR(i,1,n+1)

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;
#define fcout cout << fixed << setprecision(18)

int main() {
  int H, W, A, B;
  cin >> H >> W >> A >> B;

  rep0(i, H) {
    rep0(j, W) {
      if ((i < B && j < A) || (i >= B && j >= A)) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << BR;
  }

  return 0;
}

Measured memory_bytes: 1280
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
mod = 998244353
ans = 1



n = int(readline())
d = list(map(int, readline().split()))

import collections
d_count = collections.Counter(d)

if d[0] != 0:
    print(0)
    sys.exit()
if d_count[0] != 1:
    print(0)
    sys.exit()
    

for i in range(n):
     ans = ans * (d_count[i] ** d_count[i+1]) % mod
     
     if d_count[i] == 0 and d_count[i+1] != 0:
         print(0)
         sys.exit()
print(ans)
    

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

using namespace std;

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define int long long
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int,int>
#define INF LLONG_MAX
#define EPS 1e-9
#define all(v) (v).begin(),(v).end()
#define sq(x) ((x)*(x))
#define foreach(it, v) for(auto it=(v).begin(); it != (v).end(); ++it)
#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)


#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;}
 
template<typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);}
 
typedef long double dbl;
bool codejam = 0;

const int MOD = 1000*1000*1000 + 7;
const int NMAX = 1000*1000 + 11;

int arr[NMAX];
int n,m,p,q,k,a,b,c;
char ch;
vector<int> v;
vector<int> gr[200011];
multiset<int> s;
int ans[NMAX];

void dfs(int cur, int par){

    s.insert(arr[cur]);

    auto it = s.lower_bound(arr[cur]);
    it++;
    int del = -1;

    if(it != s.end()){
        del = *it;
        s.erase(it);
    }

    ans[cur] = s.size();

    for(auto ch:gr[cur]){
        // cout<<ch<<" "<<cur<<" "<<par<<"\n";
        if(ch!=par){
            dfs(ch,cur);
        }
    }
    if(del != -1) s.insert(del);

    s.erase(s.find(arr[cur]));
    return;

}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    int u,v;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        gr[u].pb(v);
        gr[v].pb(u);
    }

    dfs(1,1);

    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
}

int32_t main(){ fio;
    int t = 1;
    int cs = 1;
    // cin>>t;
    while(t--){
        if(codejam){
            cout<<"Case #"<<cs<<": ";
        }
        cs++;
        solve();
        cout<<"\n";
    }
}

Measured memory_bytes: 32020
n = int(input())
s = input()
w = [0]
e = [0]

for i in range(1,n+1):
    w.append(w[i-1] + (s[i-1]=='W'))
    e.append(e[i-1] + (s[i-1]=='E'))

ans = n
for i in range(1,n+1):
    ans = min(ans, w[i-1]+e[n]-e[i])
print(ans)


Measured memory_bytes: 27116
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import java.util.Arrays;

public class Main {

	public static class SkewHeap<T extends Comparable<? super T>> {

		private static class Node<T> {
			Node<T> left, right;
			T value; // value に null を入れると死ぬ.

			public Node(T value){ this.value = value; }
			public Node(Node<T> n){
				this.left = n.left; this.right = n.right;
				this.value = n.value;
			}

			public String toString(){ // これはデバッグ用なので削ってもいい.
				return "[" + this.left + "] " + this.value + " [ " + this.right + " ]";
			}
		}

		private static <T extends Comparable<? super T>> Node<T> meld(Node<T> a, Node<T> b){
			if(a == null){ return b; }
			if(b == null){ return a; }
			if(a.value.compareTo(b.value) > 0){ return meld(b, a); } // > で Min, < で Max
			a.right = meld(a.right, b);
			{ Node<T> tmp = a.left; a.left = a.right; a.right = tmp; } // swapするだけ!
			return a;
		}

		private Node<T> root = null;
		// 基本的な操作
		public void add(T value){ root = meld(root, new Node<T>(value)); }
		public void pop(){ root = meld(root.left, root.right);}
		public void merge(SkewHeap<T> other){ root = meld(this.root, other.root); }
		// ユーティリティ
		public T poll(){ T val = peek(); pop(); return val; }
		public T peek(){ return root.value; }
		public boolean isEmpty(){ return root == null; }
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		SkewHeap<Integer> heap = new SkewHeap<Integer>();

		while(true){
			final String ops = sc.next();
			if("end".equals(ops)){ break; }
			
			if("extract".equals(ops)){
				System.out.println(-(heap.poll()));
			}else{
				heap.add(-sc.nextInt());
			}
		}
	}
		
	public static class Scanner {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() {
			try {
				while (!hasNext()) {tok = new StringTokenizer(br.readLine());}
			} catch(IOException e){ /* ignore */ }
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() {
			getLine(); return tok.nextToken();
		}

		public int nextInt(){
			return Integer.parseInt(next());
		}
		// 他のnextXXXもXXX.parseXXX()メソッドを使って作れるので省略

		public void close() {
			try{ br.close(); } catch (IOException e){ /*ignore*/ }
		}
	}
}

Measured memory_bytes: 218400
#include <iostream>
#include <cstring>
#include <algorithm>
#include <list>
#include <map>
#include <cmath>
#include <string>
#include <cstdio>
#include <vector>
 
using namespace std;

typedef long long ll;
typedef long double ld;
#define L(ID) ((ID*2)+1)
#define R(ID) ((ID*2)+2)
#define M(L,R) ((L+R)/2)
#define forr(start,end) for(int i = start; i < end; i++)
#define gap ' '
 
const int MAXN = 1e5+5;
ll n = 0, a[MAXN], BIT[MAXN];

ll largest(ll a, ll b){
	return (a<b)?b:a;
}
int smallest(ll a, ll b){
	if(a < b)return a;
	return b;
}
int sign(int v){
	if(v < 0)return -1;
	return v>0;
}
ll solve(int checking){
	ll cnt = 0;
	int sum = 0, prev_sum = checking, add = 0;
	for(int i = 0; i < n; ++i){
		sum+=a[i];
		if(prev_sum < 0 and sum <= 0){
			add=-sum+1;
			sum+=add;
			cnt+=llabs(add);
		}
		if(prev_sum > 0 and sum >= 0){
			add=-sum-1;
			sum+=add;
			cnt+=llabs(add);
		}
		prev_sum = sum;
	}
	return cnt;
}

int main() {	
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	cout << min(solve(1), solve(-1)) << endl;





    return 0;
}	

Measured memory_bytes: 1024
#include <stdint.h>
#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

int main(int argc, char *argv[]) {
  int X, Y, Z;
  std::cin >> X >> Y >> Z;
  X -= Z;
  if (X < 0) X = 0;
  std::cout << (X / (Y + Z)) << std::endl;

  return 0;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
sa,lw=set(),[0]*n
for _ in range(m):
  p,s=input().split()
  if p in sa: continue
  if s=='AC': sa.add(p)
  else: lw[int(p)-1]+=1
print(len(sa),sum(lw[int(p)-1] for p in sa))

Measured memory_bytes: 14828
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		
		if ( a.equals("H") && b.equals("H") ) System.out.println("H");
		else if ( a.equals("H") && b.equals("D") ) System.out.println("D");
		else if ( a.equals("D") && b.equals("H") ) System.out.println("D");
		else if ( a.equals("D") && b.equals("D") ) System.out.println("H");
	}
}


Measured memory_bytes: 21844
// Created by sz
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    cout <<(ll)n*(n-1)/2 << "\n";
    return 0;
}



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

void printArray(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
}

int insertionSort(int a[], int n, int g) {
    int cnt = 0;

    for (int i = g; i < n; i++) {
        int v = a[i];
        int j = i - g;

        while (j >= 0 && v < a[j]) {
            a[j + g] = a[j];
            j -= g;
            cnt++;
        }

        a[j + g] = v;
    }

    return cnt;
}

int shellSort(int a[], int n) {
    int cnt = 0;

    vector<int> g;
    g.push_back(1);
    for (int i = 4; i < n; i = 3 * i + 1) {
        g.push_back(i);
    }

    int m = g.size();
    cout << m << endl;

    for (int i = m - 1; i >= 0; i--) {
        if (i != m - 1) cout << " ";
        cout << g.at(i);

        cnt += insertionSort(a, n, g[i]);
    }
    cout << endl;

    return cnt;
}

int main() {
    int n;
    cin >> n;

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

    int cnt = shellSort(a, n);

    cout << cnt << endl;
    printArray(a, n);
}

Measured memory_bytes: 7000
#include <bits/stdc++.h>
using namespace std;
 
#define int         long long
#define endl        "\n"
#define pii         pair<int, int>

const int mod = 1e9+7;
const int MAXN = 1e5+5;
const int N = 1e5+5;

int fac[N];
int spf[MAXN]; 

void pre(int p) {
    fac[0] = 1;
    for(int i=1; i<N; i++) {
        fac[i] = (fac[i-1] * i) % p;
    }
}


void sieve() 
{ 
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++) spf[i] = i; 
    for (int i=4; i<MAXN; i+=2) spf[i] = 2; 
  
    for (int i=3; i*i<MAXN; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (int j=i*i; j<MAXN; j+=i) if (spf[j]==j) spf[j] = i; 
        } 
    } 
} 

vector<int> getFactorization(int x) 
{ 
    vector<int> ret; 
    while (x != 1) 
    { 
        ret.push_back(spf[x]); 
        x = x / spf[x]; 
    } 
    return ret; 
} 

unsigned long long power(unsigned long long x, 
                         int y, int p) 
{ 
    unsigned long long res = 1; // Initialize result 
  
    x = x % p; // Update x if it is more than or 
    // equal to p 
  
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
unsigned long long modInverse(unsigned long long n, int p) 
{ 
    return power(n, p - 2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
unsigned long long nCr(unsigned long long n, 
                                 int r, int p) 
{ 
    // Base case 
    if (r == 0) return 1; 
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
}

///////////////////////////////////////////////////////////////////////////////////////////////////
 
void solve(int TC) { 
   int n; cin >> n;
   set<int> s;
   int ans =0;
   for(int i=0; i<n; i++) {
       int x; cin >> x;
       if(s.count(x)) {
           s.erase(x);
       } else {
           s.insert(x);
           
       }
   }
   cout << (int)s.size();
}
 
signed main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);
 
 
    int T = 1;
    //cin >> T;
    for(int i=1; i<=T; i++) {
        solve(i);
    }
    return 0;
 
}

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

using namespace std;
using ll = long long;

int main(){
    int X,Y;cin >> X >> Y;
    int ans = 0;
    if(X == 3)ans += 100000;
    if(X == 2)ans += 200000;
    if(X == 1)ans += 300000;
    if(Y == 3)ans += 100000;
    if(Y == 2)ans += 200000;
    if(Y == 1)ans += 300000;
    if(X == 1 && Y == 1)ans += 400000;
    cout<<ans<<endl;
}

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

const int MAX = 105;
int n;
int am[MAX][MAX];
int d[MAX], f[MAX], t, color[MAX], nt[MAX];

int next(int u) {
  for (int v = nt[u]; v < n; v++) {
    nt[u] = v + 1;
    if (am[u][v]) return v;
  }
  return -1;
}

void dfs_visit(int r) {
  stack<int> S;
  S.push(r);
  color[r] = 1;
  d[r] = ++t;

  while (!S.empty()) {
    int u = S.top();
    int v = next(u);
    if (v != -1) {
      if (color[v] == 0) {
      color[v] = 1;
      d[v] = ++t;
      S.push(v);
      }
    } else {
    S.pop();
    color[u] = 2;
    f[u] = ++t;
    }
  }
}

int main() {
  int u, k, v;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      cin >> v;
      am[u-1][v-1] = 1;
    }
  }

  for (int u = 0; u < n; u++) {
    if (color[u] == 0) dfs_visit(u);
  }

  for (int i = 0; i < n; i++) {
    cout << i + 1 << " " << d[i] << " " << f[i] << endl;
  }
  return 0;
}



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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int minus = 0, min_a = pow(2, 30);
  int i;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] < 0) {
      minus++;
    }
    a[i] = fabs(a[i]);
    min_a = min(min_a, a[i]);
  }
  long long result = 0;
  if (minus % 2 != 0) {
    result -= min_a * 2;
  }
  for (i = 0; i < n; i++) {
    result += a[i];
  }
  cout << result << endl;
  return 0;
}


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

using namespace std;

char s[555][555];
bool b[555][555];
int n,m;

int main()
{
	int i,j,k,x,y;
	
	scanf("%d%d",&n,&m);
	
	for(i=0;i<n;i++){
		scanf("%s",s[i]);
	}
	
	for(i=0;i<m;i++){
		b[0][i] = 1;
		if(i & 1){
			for(j=0;j<n-1;j++) b[j][i] = 1;
		}
	}
	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(s[i][j] == '#' || b[i][j]) printf("#");
			else printf(".");
		}
		printf("\n");
	}
	
	printf("\n");
	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(s[i][j] == '#' || !b[i][j]) printf("#");
			else printf(".");
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 1280
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
# 勇者1...1番目・2番目の街で、B_1体まで
# 勇者2...2番目・3番目の街で、B_2体まで
# 勇者N...N番目・(N+1)番目の街で、B_N体まで

# 1番目の街は1番目の勇者が救う
# 1番目の勇者は1番目の街のモンスターを全力でmin(A_1,B_1) 体倒す
# 残った力で2番目の街のモンスターを全力でmin(A_2,B_1−min(A_1,B_1))体倒す
# 2番目の街に残ったモンスターは2番目の勇者が倒す
# これを繰り返す

ans = sum(A)
for i in range(N):
  if A[i] >= B[i]: A[i] -= B[i]
  else:
    # A[i] < B[i]
    B[i] -= A[i]
    A[i] = 0
    A[i+1] = max(A[i+1]-B[i], 0) 

# 初めのモンスター数 - 残ったモンスター数 = 勇者たちが倒した数
ans -= sum(A)
print(ans)

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

int main(){
	int n, d, ans;
	cin >> n >> d;
	
	d = d * 2 + 1;
	if(n % d != 0) ans = n / d + 1;
	else ans = n / d;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define Rep(i, m, n) for(ll i = m; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x, y, z) max((x), max((y), (z)))
#define tmin(x, y, z) min((x), min((y), (z)))
#define MINUS(a) memset(a, 0xff, sizeof(a))
#define ZERO(a) memset(a, 0, sizeof(a))
const ll INF = 1LL << 60;
const ll MM = 1000000000; const ll MOD = MM + 7; const ll MMM=9223372036854775807;//2^63 -1
#define ADD(a,b) a = (a + ll(b)) % MOD
#define MUL(a,b) a = (a * ll(b)) % MOD
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
template<class T> inline bool chmin(T& a, T b){ if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true;} return false;}
template<typename A, size_t N, typename T> void FILL(A (&array)[N], const T &val){ fill( (T*)array, (T*)(array+N), val );}
struct edge{ ll from, to, cost; };
// struct edge{ ll to, cost; };
// using Graph = vector<vector<ll>>;  // 重み無し
using Graph = vector<edge>;  // 辺
// using Graph = vector<vector<edge>>;  // 重み付き
ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
ll ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1}, ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//cout << fixed << setprecision(10);

const ll MAX_E = 2000, MAX_V = 1000;  // 制約に従って決める
ll V, E;  // 入力で受け取る

Graph es(MAX_E);  // 0-basedにして順番に辺を入れる
ll d[MAX_V];  // ある頂点までの最短路(0-based)


bool bellman_ford(ll s){  // 始点の頂点番号が引数(0-based)
    FILL(d, INF);
    d[s] = 0;
    rep(loop, V-1){
        bool update = false;
        rep(i, E){
            edge e = es[i];
            if(d[e.from] != INF && chmin(d[e.to], d[e.from] + e.cost)) update = true;
        }
        // V-1回以内に更新無くなれば負の閉路なし
        if(!update) return true;
    }
    // もうV回回してV-1に更新がないか調べる
    rep(loop, V){
        bool update = false;
        rep(i, E){
            edge e = es[i];
            // 頂点V-1に更新があれば
            if(d[e.from] != INF && chmin(d[e.to], d[e.from] + e.cost) && e.to == V-1) update = true;
        }
        // 負の閉路があり無限に更新可能
        if(update) return false;
    }
    return true;
}


int main(){
    cin >> V >> E;
    rep(i, E){
        ll a, b, c; cin >> a >> b >> c; a--, b--, c = -c;
        es[i] = edge{a, b, c};
    }
    // 負の閉路なし
    if(bellman_ford(0)) cout << -d[V-1] << endl;
    else cout << "inf" << endl;
}


Measured memory_bytes: 3680
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int N,a[20000],b[20000];
int main(){
	cin>>N;
	rep(i,N) a[i]=b[N-1-i]=30000*i+1;
	rep(i,N){
		int p;
		cin>>p;
		p--;
		a[p]+=i;
	}
	rep(i,N) cout<<a[i]<<" ";
	puts("");
	rep(i,N) cout<<b[i]<<" ";
	puts("");
}


Measured memory_bytes: 768
def read():
    return [int(x) for x in str.split(raw_input())]

n = read()[0]
a = read()
odd, even = 0, 0

for i in a:
    if (i%2 == 0):
        even = even+1
    else:
        odd = odd+1

if (odd%2 == 0):
    print("YES")
else:
    print("NO")


Measured memory_bytes: 11812
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
 
using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;
int main(void) {
    Int n, k;
    cin >> n >> k;
    if (n % k == 0) {
        cout << 0 << endl;
    } else {
        cout << 1 << 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);
        int x = sc.nextInt();
        int y = sc.nextInt();

        int res = 0;
        if(x <= 3) {
            res += 100000 * (4-x);
        }
        if(y <= 3) {
            res += 100000 * (4-y);
        }
        if(x == 1 && y == 1) {
            res += 400000;
        }
        System.out.println(res);

    }
}


Measured memory_bytes: 21972
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def calc(p, N):
    ans = 0
    while N != 0:
        N //= p
        ans += N
    return ans

N = int(input())
P = primes(N)
count = []
for i in range(len(P)):
    count.append(calc(P[i], N))
ans = 0
for i in range(len(P)):
    if count[i] >= 74:
        ans += 1

for i in range(len(P)-1):
    for j in range(i+1, len(P)):
        if count[i] >= 2 and count[j] >= 24:
            ans += 1
        if count[i] >= 24 and count[j] >= 2:
            ans += 1
        if count[i] >= 4 and count[j] >= 14:
            ans += 1
        if count[i] >= 14 and count[j] >= 4:
            ans += 1

for i in range(len(P)-2):
    for j in range(i+1, len(P)-1):
        for k in range(j+1, len(P)):
            if count[i] >= 2 and count[j] >= 4 and count[k] >= 4:
                ans += 1
            if count[i] >= 4 and count[j] >= 2 and count[k] >= 4:
                ans += 1
            if count[i] >= 4 and count[j] >= 4 and count[k] >= 2:
                ans += 1

print(ans)

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

typedef long long ll;
const int N = 1000 + 10;
int v[N*2], u[N*2], cost[N*2];
ll dis[N];
bool vis[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &v[i], &u[i], &cost[i]);
        cost[i] = -cost[i];
    }
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[1] = 0;
    for(int i = 1; i <= n-1; i++)
        for(int j = 1; j <= m; j++)
            dis[u[j]] = min(dis[u[j]], dis[v[j]] + cost[j]);
    ll ans = -dis[n];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(dis[u[j]] > dis[v[j]] + cost[j])
            {
                dis[u[j]] = dis[v[j]] + cost[j];
                vis[u[j]] = true;
            }
            //if(dis[v[j]] == true) dis[u[j]] = true;
        }
    if(vis[n]) puts("inf");
    else printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define INF 1000000010
const ll MOD = 1000000007;

int main(){
    string s;
    cin>>s;
    int ans=INF;
    int n=s.size();
    rep(i,n-1){
        if(s[i]!=s[i+1]){
            ans=min(ans,max(i+1,n-(i+1)));
        }
    }
  	if(ans==INF) ans=n;
    cout<<ans<<endl;
}

Measured memory_bytes: 3688
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
using namespace std;
using ll = long long;

int main() {
	int N, X, T;
	int count = 0;
	int time = 0;
	cin >> N >> X >> T;
	count = N / X;
	if (N % X == 0) {
		time = count * T;
	}
	else {
		time = (count+1) * T;
	}
	cout << time << endl;
	return 0;
}

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5;
int pre[N+2];
int post[N+2];
int p[N+2];
int loc[N+2];
int main()
{
    memset(pre,-1,sizeof pre);
    memset(post,-1,sizeof post);
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
        loc[p[i]] = i;
    }

    set<int> available;
    available.insert(0);
    available.insert(n+1);

    LL ans = 0;
    for(LL k = n; k >= 1; k--)
    {
        LL aft = *available.upper_bound(loc[k]);
        LL bef = *(--available.upper_bound(loc[k]));

        post[bef] = loc[k];
        pre[aft] = loc[k];
        pre[loc[k]] = bef;
        post[loc[k]] = aft;

        if(bef >= 1)
            ans += k*(bef-pre[bef])*(aft-loc[k]);
        if(aft <= n)
            ans += k*(loc[k]-bef)*(post[aft]-aft);
        
        available.insert(loc[k]);
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 9760
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int w,a,b;
    cin >> w >> a >> b;
    if(a > b){
        int t = a;
        a = b;
        b = t;
    }

    if(a+w > b){
        cout << 0 << endl;
        return 0;
    }
    cout << abs(a+w-b) << endl;
}

Measured memory_bytes: 3680
from operator import mul
from functools import reduce

N,K = map(int, input().split())
mod = 10**9 +7

if N - K > K - 1:
    m = K
else:
    m = N - K + 1

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(1,K+1):
    if i <= m:
        a = cmb(K-1, i-1)%mod
        b = cmb(N-K+1, N-K-i+1)%mod
        print(a*b%mod)
    else:
        print(0)

Measured memory_bytes: 3944
n,m=map(int,input().split())
a=[]
c=[0]*n
cnt=0
b=[0]*n
for _ in range(m):
  p,s=input().split()
  p=int(p)
  p-=1
  if s=="AC":
    a.append(p)
    if c[p]==0:
          c[p]=1
  else:
        if c[p]==0:    
          b[p]+=1
a=list(set(a))
for i in a:
  cnt+=b[i]
print(len(set(a)),cnt)

Measured memory_bytes: 59352
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        double a = Double.parseDouble(sc.next());
        System.out.println(String.format("%.6f", a * a * 3.141592653589) + " " + String.format("%.6f", a * 2 * 3.141592653589));
    }
}


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

int main()
{
	double x,y;
	cin >> x >> y;
	double z = y/x;

	int count = 0;
	for(double i=1;i<x;i++){
		for(double j=1;j<y;j++){
			if(j/i==z){
				count++;
			}else if(j/i>z){
				break;
			}
		}
	}

	int answer = x+y-count;

	cout << answer << endl;

	return 0;
}


Measured memory_bytes: 3224
import java.util.Scanner;


public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++)
      arr[i] = sc.nextInt();
    int now = 1;
    int cnt = 0;
    for(int i = 0; i < n; i++) {
      if(arr[i]==now) {
        now++;
        cnt++;
      }
    }
    if(cnt!=0) System.out.println(n-cnt);
    else System.out.println(-1);
  }

}


Measured memory_bytes: 87796
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

#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 pb push_back
#define eb emplace_back

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;

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

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    else return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

template<class T>
void dcomb(T n,T m, string s){
    if(n==0) cout << s << endl;
    else {
        for(T i=0; i<m; ++i){
            dcomb(n-1,m,s+to_string(i));
        }
    }
}

ll  INF = 1e9+7;

int main(){
    ll n,w;
    cin >> n >> w;
    vpll wv(n);
    rep(i,n) cin >> wv[i].first >> wv[i].second;
    vector<vector<ll>> dp(n+1,vector<ll>(100010,INF));
    dp[0][0] = 0;
    for(ll i = 0; i<n; i++){
        for(ll value = 0; value<100010; ++value){
            if(value-wv[i].second>=0){
                chmin(dp[i+1][value],dp[i][value-wv[i].second]+wv[i].first);
            }
            chmin(dp[i+1][value],dp[i][value]);
        }
    }
    for(ll i = 100009; i>=0; --i){
        if(dp[n][i]<=w){
            cout << i << endl;
            break;
        }
    }
}

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

int main(){
    ll ans = 0;
    ll n; cin >> n;

    ans = 0.5L * n * (n - 1);

    put(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
lint ans = 1;
int K;
class Node;
vector<Node> V;
class Node {
    public:
    int idx;
    vector<int> nbr;
    int vst = 0;
    void dfs(int lastnbr) {
        V[idx].vst = 1;
        int c = K - lastnbr;
        if(c <= 0) {
            cout << 0;
            exit(0);
        }
        ans = (ans * c) % MOD;
        int a = 0;
        for(int x : nbr) {
            if(V[x].vst == 0) {
                V[x].dfs(nbr.size() - a);
                a++;
            }
        }
    }
    Node() {

    }
};
int main()
{
    int N;
    cin >> N >> K;
    V = vector<Node>(N);
    REP(i, N) {
        V[i].idx = i;
    }
    REP(i, N-1) {
        int a, b;
        cin >> a >> b;
        V[a-1].nbr.push_back(b-1);
        V[b-1].nbr.push_back(a-1);
    }
    V[0].dfs(0);
    cout << ans << endl;
}

Measured memory_bytes: 9600
n = gets.to_s.to_i

ans = n
(n+1).times do |i|
  
  c = 0
  t = i
  while t > 0
    c += t%6
    break if ans <= c
    t /= 6
  end
  next if ans <= c
  t = n-i
  while t > 0
    c += t%9
    break if ans <= c
    t /= 9
  end
  
  ans = c if ans > c
end

puts ans

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    string s;
    cin>>s;
    int left, right;
    rep(i, s.size()){
        if(s[i] == 'Z') right = i;
    }
    reverse(s.begin(), s.end());
    rep(i, s.size()){
        if(s[i] == 'A') left = s.size()-1-i;
    }
    cout<<right-left+1<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <list>
#include <math.h>
#include <algorithm>
#include <chrono>
#include <random>
#include <queue>
#include <fstream>
#include <iterator> // std::back_inserter
#include <chrono>
#include <string>
#include <stdio.h>
#include <iomanip>
#include <float.h>
#include <cassert>
#include <functional>

using namespace std;

int main(int argc, char *argv[])
{
    int a, b;
    cin >> a >> b;

    int ans = 0;

    if (a > b)
    {
        ans += a;
        a -= 1;
    }
    else
    {
        ans += b;
        b -= 1;
    }

    if (a > b)
    {
        ans += a;
        a -= 1;
    }
    else
    {
        ans += b;
        b -= 1;
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, Y: int):
    for i in range(N + 1):
        for j in range(N - i + 1):
            k = N - i - j
            if 10000 * i + 5000 * j + 1000 * k == Y:
                print(i, j, k)
                return
    print('-1 -1 -1')
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, Y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
a = int(input())
n,k= map(int,input().split())
x = list(map(int,input().split()))
aa = bb = cc = 0
for i in range(a):
    if x[i] <= n:
        aa+=1
    elif n+1 <= x[i] <= k:
        bb+=1
    else:cc+=1
print(min(aa,bb,cc))
        

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

int main() {
  int N;
  cin >> N;
  
  int count=0;
  for(long long A=1; A<= N-1; A++){
    count+=(N-1)/A;
    
      
    
  }
  
    
  
  
 
 cout << count<< endl;
     
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstdio>
#include<algorithm>

int n,m,L,R;
std::pair<int,bool> P[200050];
const int mod=1000000007;

std::pair<int,int> Q[100050];
int tot,top;
int tmpx[200050],tmpy[200050],topx,topy;

inline void chkinc(int &A){A+=A>>31&mod;}

class Fenwick{
	private:
		int orig[200050];
		int F[200050],Fenwicklim;
	public:
		void setlim(int x){Fenwicklim=x;}
		void modify(int x,int v){int dex=v-orig[x];chkinc(dex),orig[x]=v;while (x<=Fenwicklim) chkinc(F[x]+=dex-mod),x+=x&-x;}
		int query(int x){int ret=0;while (x) chkinc(ret+=F[x]-mod),x&=x-1;return ret;}
}B;

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&P[i].first),P[i].second=0;
	for (int i=1;i<=m;i++) scanf("%d",&P[i+n].first),P[i+n].second=1;
	std::sort(P+1,P+n+m+1);
	L=1,R=n+m;
	while (!P[L].second) L++;
	while (!P[R].second) R--;
	for (int i=L,lst=i;i<=R;i++){
		if (P[i].second) lst=i;
		else Q[++tot].first=P[i].first-P[lst].first,tmpx[++topx]=Q[tot].first;
	}
	top=tot;
	for (int i=R,lst=i;i>=L;i--){
		if (P[i].second) lst=i;
		else Q[top--].second=P[lst].first-P[i].first,tmpy[++topy]=Q[top+1].second;
	}

	tmpx[++topx]=-1,tmpy[++topy]=-1;
	tmpx[++topx]=1000000001,tmpy[++topy]=1000000001;
	Q[++tot]=std::make_pair(-1,-1);
	Q[++tot]=std::make_pair(1000000001,1000000001);

	std::sort(Q+1,Q+tot+1);
	tot=std::unique(Q+1,Q+tot+1)-Q-1;
	std::sort(tmpx+1,tmpx+topx+1);
	topx=std::unique(tmpx+1,tmpx+topx+1)-tmpx-1;
	std::sort(tmpy+1,tmpy+topy+1);
	topy=std::unique(tmpy+1,tmpy+topy+1)-tmpy-1;
	for (int i=1;i<=tot;i++){
		Q[i].first=std::lower_bound(tmpx+1,tmpx+topx+1,Q[i].first)-tmpx;
		Q[i].second=std::lower_bound(tmpy+1,tmpy+topy+1,Q[i].second)-tmpy;
	}

	B.setlim(Q[tot].second);
	B.modify(1,1);
	for (int l=2,r;l<tot;l=r+1){
		r=l;
		while (r<tot-1&&Q[l].first==Q[r+1].first) r++;
		for (int i=r;i>=l;i--) B.modify(Q[i].second,B.query(Q[i].second));
	}
	printf("%d\n",B.query(Q[tot].second));
}


Measured memory_bytes: 4352
import math

N,P = list(map(int,input().split()))

i = 2
l = []
while i*i <= P:
    while P%i == 0:
        P /= i
        l.append(i)
    i += 1
if P > 1:
    l.append(int(P))
if len(l) == 0:
    l.append(1)

n = list(set(l))
c = [math.floor(l.count(i)/N) for i in n]
res = 1
for m in [n_**c_ for n_,c_ in zip(n,c)]:
    if m > 0:
        res *= m

print(res)

Measured memory_bytes: 3064